Jeff Jackson's Research Interests
The bulk of my research has been in Computational Learning Theory (COLT)
and has involved developing mathematical models formally describing various
senses of learning as well as proving within these models that certain types of
learning problems can or cannot be solved efficiently. My best-known work in
this area has been the development of the Harmonic Sieve, an algorithm that
efficiently solves the problem of learning certain types of functions (DNF
expressions) in a certain relatively natural setting (using membership queries
with respect to the uniform distribution).
Recently, I have been attempting to answer a fundamental question that
should be of interest to machine learning practitioners as well as to
theoreticians: what assumptions must we make in order to reasonably be
convinced that a learning algorithm has successfully solved a given learning
problem? There are widely accepted answers to this question based on the
well-known No Free Lunch theorems
for learning; my answer (unpublished joint work with Tino Tamon) is radically
different. This research has led me to do some related work in the philosophy
of mathematics.
One other major "research" area has involved writing my textbook, Web
Technologies: A Computer Science Perspective. While this book has very
little relationship with my more theoretical research mentioned above, it
represents a tremendous amount of time spent researching (in the college term
paper sense), explaining, and illustrating various web technologies.
Finally, I've dabbled in research in a number of other areas, including pure
math, empirical machine learning, software engineering, human-computer
interaction, and astrophysics (as an undergraduate assistant).
A listing of my research publications appears below. Some links to other
information about me and some of what I'm involved in:
Textbook
Thesis
Recent non-COLT Papers
COLT Articles and Papers
- Jackson, J. C., Learning
DNF Formulas, Encyclopedia of Algorithms, Second Edition
(Ming-Yang Kao, Ed.), 2014. First edition,
2008.
- Jackson, J. C. and Wimmer, K., New
Results for Random Walk Learning, Journal of Machine Learning
Research 15, 3815-3846, 2014. Preliminary
version in Proceedings of 22nd Annual Conference on Learning Theory,
2009.
- Jackson, J. C., Lee, H. K., Servedio, R. A., Wan, A., Learning Random
Monotone DNF (preliminary version), Discrete Applied Mathematics
159(5), 259-271, 2011.
- Jackson, J. C., Uniform-Distribution
Learnability of Noisy Linear Threshold Functions with Restricted Focus of
Attention, Proceedings of 19th Annual Conference on Learning
Theory, 2006.
- Jackson, J. C., and Servedio, R. A., On Learning Random DNF Formulas Under the
Uniform Distribution, Theory of Computing 2, 2006. Preliminary version in
Proceedings of 9th International Workshop on Randomization and
Computation, RANDOM 2005.
- Jackson, J. C., and Servedio, R. A., Learning Random
log-depth Decision Trees under the Uniform Distribution, SIAM
Journal on Computing 34/5, 2005. Preliminary
version in Proceedings of the 16th Annual Workshop on Computational
Learning Theory, 2003.
- Bshouty, N. H., Jackson, J. C., and Tamon, C., Exploring
Learnability Between Exact and PAC, Journal of Computer and System
Sciences 70/4 (Special Issue on COLT 2002, invited), 2005. Preliminary
version in Proceedings of the 15th Annual Workshop on Computational
Learning Theory, 2002.
- Blum, A., Jackson, J., Sandholm, T., and Zinkevich, M., Preference
Elicitation and Query Learning, Journal of Machine Learning
Research 5 (Special Topic on Learning Theory, invited), June 2004. Preliminary
version in Proceedings of the 16th Annual Workshop on Computational
Learning Theory, 2003.
- Bshouty, N., Jackson, J., and Tamon, T., More Efficient
PAC-learning of DNF with Membership Queries Under the Uniform
Distribution, Journal of Computer and System Sciences 68, 2004.
Preliminary version in Proceedings of the 12th Annual Workshop on
Computational Learning Theory, 1999. Preliminary extended version: postscript (.ps) or portable
document format (.pdf).
- Bshouty, N., Jackson, J., and Tamon, T., Uniform-Distribution
Attribute Noise Learnability, Information and Computation 187(2),
December 2003. Preliminary version in Proceedings of the 12th Annual
Workshop on Computational Learning Theory, 1999. Preliminary extended
version: postscript (.ps) or portable document format (.pdf).
- Jackson, J., On the Efficiency of Noise-Tolerant PAC Algorithms
Derived from Statistical Queries, Annals of Mathematics and Artificial
Intelligence, 2003. Preliminary version in Proceedings of the 13th Annual
Workshop on Computational Learning Theory, 2000. Pre-print version: postscript (.ps) or portable
document format (.pdf).
- Jackson, J. C., Klivans, A. R., and Servedio, R. A., Learnability
Beyond AC0,
Proceedings of the Symposium on the Theory of Computing 2002. Preliminary
version: postscript (.ps) or portable document format (.pdf).
- Jackson, J. C., Tamon, C., and Yamakami, T., Quantum DNF
Learnability Revisited, Proceedings of Computing and Combinatorics,
8th Annual International Conference, 2002.
- Bshouty, N. H. and Jackson, J. C., Learning DNF over the Uniform
Distribution using a Quantum Example Oracle, SIAM Journal on Computing
28(3), 1999. Preliminary version in Proceedings of the Eighth Annual
Workshop on Computational Learning Theory, 1995, 118-127. Preliminary
extended version: postscript (.ps) or portable document format (.pdf).
- Jackson, J., Shamir, E., and Shwartzman, C., Learning with Queries
Corrupted by Classification Noise, Discrete Applied Mathematics
92(2-3), 1999. Preliminary version in Proceedings of the Fifth Israel
Symposium on the Theory of Computing Systems, IEEE Press, 1997. Preliminary
extended version: postscript (.ps) or portable document format (.pdf).
- Birkendorf, A., Dichterman, E., Jackson, J., Klasner, N., and Simon, H.
U., On Restricted-Focus-of-Attention Learnability of Boolean
Functions, Machine Learning 30, 1998. Preliminary version in
Proceedings of the Ninth Annual Workshop on Computational Learning Theory,
1996. Preliminary extended version: postscript (.ps)
or portable document format (.pdf).
- Jackson, J., An Efficient Membership-Query Algorithm for Learning DNF
with Respect to the Uniform Distribution, Journal of Computer and
System Sciences 55(3), 1997. Preliminary version in Proceedings of the 35th
Symposium on Foundations of Computer Science, 1994, 42-53. A preliminary extended version of this paper is available
for download.
- Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., and Rudich,
S., Weakly Learning DNF and Characterizing Statistical Query Learning
Using Fourier Analysis, Proceedings of the Twenty-Sixth Annual
Symposium on the Theory of Computing, 1994, 253-262. (Very) preliminary
version: postscript (.ps) or portable document format (.pdf).
- Blum, A., Chalasani, P., and Jackson, J., On Learning Embedded
Symmetric Concepts, Proceedings of Sixth Annual Workshop on
Computational Learning Theory, 1993, 337-346.
- Jackson, J. and Tomkins, A., A Computational Model of Teaching,
Proceedings of Fifth Annual Workshop on Computational Learning Theory,
1992, 319-326.
- Furst, M. L., Jackson, J. C., and Smith, S. W., Improved Learning of $AC^0$ Functions,
Proceedings of Fourth Annual Workshop on Computational Learning Theory,
1991, 317-325. See also Furst, M., Jackson, J., and Smith, S., Learning
$AC^0$ Functions Sampled Under Mutually Independent Distributions,
technical report CMU-CS-90-183, October 1990.
Other Work
- Zhang, H., Kann, J., Lard, C., Jackson, J., and Spencer, A., Creation
of a Resident Reference Application for Apple iOS Devices, poster,
Society of General Internal Medicine Mid-Atlantic Conference. March 16,
2012.
- Anderson, B., Jackson, J., and Sitharam, M., Descartes' Rule of Signs
Revisited, American Mathematical Monthly, May 1998.
- Jackson, J. and Craven, M., Learning Sparse Perceptrons, Advances
in Neural Information Processing Systems 8 (Conference Proceedings of
NIPS*95), 1996. Postscript (.ps) or portable document format (.pdf).
- Bruegge, B., Blythe, J., Jackson, J., and Shufelt, J., Object-Oriented
System Modeling with OMT, Proceedings of Conference on Object-oriented
Programming Systems, Languages, and Applications, 1992, 359-376.
Proceedings published as SIGPLAN Notices, vol. 27, no. 10, October 1992.
- Neuman, Frank and Erzberger, Heinz (with appendix by Jackson, J. C.),
Analysis
of sequencing and scheduling methods for arrival traffic, NASA
Technical Memorandum NASA-TM-102795, April 1990.
- Jackson, J. C. and Roske-Hofstrand, R. J., Circling: A Method of
Mouse-Based Selection without Button Presses, Proceedings of CHI, 1989
(Conference on Computer-Human Interaction), 1989, 161-166. Proceedings
published as SIGCHI Bulletin, special issue, May 1989.
- Jackson, J. C., Observations on Integrating Interactive Graphics into
Large Batch-Oriented Simulations, Proceedings of the Second Oklahoma
Workshop on Applied Computing, March 1988, 319-326.
- Palmer, I. D., Jackson, J. C., and Hones, Jr., E. W., Entry of
Solar Protons to the Plasma Sheet and Lobe of the Magnetotail at r=18RE in the Event of
April 22, 1971, Journal of Geophysical Research, Vol. 84 (1979),
2630-2640.
- Palmer, I. D., Jackson, J. C., and Hones, Jr., E. W., The
Solar Proton Event of April 16, 1970. 3. Evolution of Pitch Angle
Distribution as ≤1-MeV Protons Propagate into the High-Latitude
Magnetotail, Journal of Geophysical Research, Vol. 84 (1979),
109-119.
E-mail: Please search for my name by visiting the Duquesne University home page and selecting a
directory search from the menu.