[1]   H. Aizenstein and L. Pitt: On the learnability of disjunctive normal form formulas. Machine Learning, 19:183–208, 1995. [ML:n226835168336578].

[2]   Noga Alon and Joel H. Spencer: The Probabilistic Method. John Wiley and Sons, 2000.

[3]   D. Angluin: Queries and concept learning. Machine Learning, 2(4):319–342, 1988. [ML:u228266621966h58].

[4]   Dana Angluin and Michael Kharitonov: When won’t membership queries help? Journal of Computer and System Sciences, 50(2):336–355, 1995. [JCSS:10.1006/jcss.1995.1026].

[5]   A. Blum: Learning a function of r relevant variables (open problem). In Proc. 16th Ann. Conf. on Computational Learning Theory (COLT’03), volume 2777 of Lecture Notes in Computer Science, pp. 731–733. Springer, 2003. [COLT:fxdg79cvndr6n05r].

[6]   A. Blum: Machine learning: a tour through some favorite results, directions, and open problems. FOCS 2003 tutorial slides, available at http://www-2.cs.cmu.edu/ avrim/Talks/FOCS03/tutorial.ppt, 2003.

[7]   A. Blum, C. Burch, and J. Langford: On learning monotone boolean functions. In Proc. 39th FOCS, pp. 408–415. IEEE Computer Society Press, 1998. [FOCS:10.1109/SFCS.1998.743491].

[8]   A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich: Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proc. 26th STOC, pp. 253–262. ACM Press, 1994. [STOC:195058.195147].

[9]   B. Bollobás: Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press, 1986.

[10]   M. Golea, M. Marchand, and T. Hancock: On learning μ-perceptron networks on the uniform distribution. Neural Networks, 9(1):67–82, 1994. [NeuralNet:10.1016/0893-6080(95)00009-7].

[11]   T. Hancock: Learning kμ decision trees on the uniform distribution. In Proc. 6th Ann. Conf. on Computational Learning Theory (COLT’93), pp. 352–360. ACM Press, 1993. [ACM:168304.168374].

[12]   J. Jackson: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414–440, 1997. [JCSS:10.1006/jcss.1997.1533].

[13]   J. Jackson, A. Klivans, and R. Servedio: Learnability beyond AC⁰. In Proc. 34th STOC, pp. 776–784. ACM Press, 2002. [STOC:509907.510018].

[14]   J. Jackson and R. Servedio: Learning random log-depth decision trees under the uniform distribution. In Proc. 16th Ann. Conf. on Computational Learning Theory (COLT’03) and 7th Kernel Workshop, volume 2777 of Lecture Notes in Computer Science, pp. 610–624. Springer, 2003. [doi:10.1007/b12006, COLT:31wxjv7lb9l5].

[15]   J. Jackson and R. Servedio: On learning random DNF formulas under the uniform distribution. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), volume 3624 of Lecture Notes in Computer Science, pp. 342–353. Springer, 2005. [RANDOM:2y5933y326xhbgar].

[16]   J. Jackson and C. Tamon: Fourier Analysis in Machine Learning. ICML/COLT 1997 tutorial slides, available at http://learningtheory.org/resources.html, 1997.

[17]   M. Kearns: Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983–1006, 1998. [JACM:293347.293351].

[18]   M. Kearns, M. Li, L. Pitt, and L. Valiant: On the learnability of Boolean formulae. In Proc. 19th STOC, pp. 285–295. ACM Press, 1987. [STOC:28395.28426].

[19]   M. Kearns, M. Li, L. Pitt, and L. Valiant: Recent results on Boolean concept learning. In Proc. 4th Internat. Workshop on Machine Learning, pp. 337–352. Morgan Kaufmann, 1987.

[20]   M. Kearns and U. Vazirani: An introduction to computational learning theory. MIT Press, Cambridge, MA, 1994.

[21]   A. Klivans, R. O’Donnell, and R. Servedio: Learning intersections and thresholds of halfspaces. In Proc. 43rd FOCS, pp. 177–186. IEEE Computer Society Press, 2002. [FOCS:10.1109/SFCS.2002.1181894].

[22]   L. Kučera, A. Marchetti-Spaccamela, and M. Protassi: On learning monotone DNF formulae under uniform distributions. Information and Computation, 110:84–95, 1994. [IandC:10.1006/inco.1994.1024].

[23]   Y. Mansour: Learning Boolean functions via the Fourier transform, pp. 391–424. Kluwer Academic Publishers, 1994.

[24]   C. McDiarmid: On the method of bounded differences. In Surveys in Combinatorics 1989, pp. 148–188. London Mathematical Society Lecture Notes, 1989.

[25]   R. Servedio: On learning monotone DNF under product distributions. In Proc. 14th Ann. Conf. on Computational Learning Theory (COLT’01), volume 2111 of Lecture Notes in Computer Science, pp. 558–573. Springer, 2001. [COLT:3j42gw4570jb08yt].

[26]   L. Valiant: A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. [CACM:1968.1972].

[27]   K. Verbeurgt: Learning DNF under the uniform distribution in quasi-polynomial time. In Proc. 3rd Ann. Workshop on Computational Learning Theory (COLT ’90), pp. 314–326. Morgan Kaufmann, 1990. [ACM:92571.92657].