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:

• My official Duquesne home page, which includes links to my courses
• Duquesne University's Department of Mathematics and Computer Science
• Duquesne University's Computational Mathematics Program
• Work by some of my research students:
  • Wenzhu Bi (MS thesis)
    
  • Miao Chen (MS thesis) [ Warning: some of the claimed results are apparently incorrect. Contact me for details. ]
    
  • Livia Overand (undergraduate research)
  • Marisa Smith (MS thesis related to NFL theorems for optimization)
    

Textbook

• Web Technologies: A Computer Science Perspective, Prentice Hall, 2007.

Thesis

• The Harmonic Sieve: A Novel Application of Fourier Analysis to Machine Learning Theory and Practice, PhD Thesis, Carnegie Mellon University, 1995, technical report CMU-CS-95-183 (zipped PDF format).

Recent non-COLT Papers

• Jackson, J.C., What is a Theorem?, unpublished paper inviting discussion at drjeffjackson.blogspot.com, 2017.
• Jackson, J. C., Randomized Arguments are Transferable (pre-print). Philosophia Mathematica 17(2), pp. 363-368, 2009. Journal version.

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.