[1]   M. Ajtai, J. Komlós, and E. Szemerédi: An O(nlog n) sorting network. Combinatorica, 3(1):1–19, 1983. [doi:10.1007/BF02579338].

[2]   E. Allender, L. Hellerstein, P. McCabe, T. Pitassi, and M. Saks: Minimizing DNF formulas and AC_d⁰ circuits given a truth table. In Proc. 21st IEEE Conf. Comput. Complex. (CCC), pp. 237–251. IEEE Comp. Soc. Press, 2006. [CCC:10.1109/CCC.2006.27].

[3]   R. Beals, T. Nishino, and K. Tanaka: On the complexity of negation-limited Boolean networks. SIAM J. Comput., 27(5):1334–1347, 1998. [SICOMP:10.1137/S0097539794275136].

[4]   I. Benjamini, G. Kalai, and O. Schramm: Noise sensitivity of Boolean functions and applications to percolation. Publ. Math. Inst. Hautes Etudes Sci., 90:5–43, 1999.

[5]   S. J. Berkowitz: On some relationships between monotone and non-monotone circuit complexity. Technical report, Technical Report, University of Toronto, 1982.

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

[7]   A. Blum, M. Furst, M. Kearns, and R. Lipton: Cryptographic primitives based on hard learning problems. In Proc. Advances in Cryptology – CRYPTO’93, number 773 in LNCS, pp. 278–291. Springer, 1993. [doi:10.1007/3-540-48329-2].

[8]   A. Blum, K. Ligett, and A. Roth: A learning theory perspective on data privacy: New hope for releasing useful databases privately. In Proc. 40th STOC, pp. 609–618. ACM Press, 2008. [STOC:10.1145/1374376.1374464].

[9]   N. Bshouty and C. Tamon: On the Fourier spectrum of monotone functions. J. ACM, 43(4):747–770, 1996. [JACM:10.1145/234533.234564].

[10]    D. Dachman-Soled, H. K. Lee, T. Malkin, R. A. Servedio, A. Wan, and H. Wee: Optimal cryptographic hardness of learning monotone functions. In Proc. 35th Intern. Colloq. Automata, Languages and Programming, Part I, pp. 36–47. Springer-Verlag, 2008. [doi:10.1007/978-3-540-70575-8_4].

[11]   V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami: New results for learning noisy parities and halfspaces. In Proc. 47th FOCS, pp. 563–576. IEEE Comp. Soc. Press, 2006. [FOCS:10.1109/FOCS.2006.51].

[12]   O. Goldreich, S. Goldwasser, and S. Micali: How to construct random functions. J. ACM, 33(4):792–807, 1986. [JACM:10.1145/6490.6503].

[13]   O. Goldreich, S. Goldwasser, and A. Nussboim: On the implementation of huge random objects. In Proc. 44th FOCS, pp. 68–79. IEEE Comp. Soc. Press, 2003. [FOCS:10.1109/SFCS.2003.1238182].

[14]   J. Håstad, R. Impagliazzo, L. Levin, and M. Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. [SICOMP:10.1137/S0097539793244708].

[15]   A. Healy, S. Vadhan, and E. Viola: Using nondeterminism to amplify hardness. SIAM J. Comput., 35(4):903–931, 2006. [SICOMP:10.1137/S0097539705447281].

[16]   J. Kahn, G. Kalai, and N. Linial: The influence of variables on Boolean functions. In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [FOCS:10.1109/SFCS.1988.21923].

[17]   S. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith: What can we learn privately? In Proc. 49th FOCS, pp. 531–540. IEEE Comp. Soc. Press, 2008. [FOCS:10.1109/FOCS.2008.27].

[18]   M. J. Kearns, M. Li, and L. G. Valiant: Learning Boolean formulas. J. ACM, 41(6):1298–1328, 1994. [JACM:10.1145/195613.195656].

[19]   M. Kharitonov: Cryptographic hardness of distribution-specific learning. In Proc. 25th FOCS, pp. 372–381. IEEE Comp. Soc. Press, 1993. [FOCS:10.1109/SFCS.1993.366850].

[20]   M. Kharitonov: Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution. J. Comput. System Sci., 50(3):600–610, 1995. [JCSS:10.1006/jcss.1995.1046].

[21]   A. Klivans, R. O’Donnell, and R. Servedio: Learning intersections and thresholds of halfspaces. J. Comput. System Sci., 68(4):808–840, 2004. [JCSS:10.1016/j.jcss.2003.11.002].

[22]   N. Linial, Y. Mansour, and N. Nisan: Constant depth circuits, Fourier transform and learnability. J. ACM, 40(3):607–620, 1993. [JACM:10.1145/174130.174138].

[23]   Y. Mansour: Learning Boolean functions via the Fourier transform. In Theoretical Advances in Neural Computation and Learning, pp. 391–424. Kluwer Academic Publishers, 1994.

[24]   E. Mossel and R. O’Donnell: On the noise sensitivity of monotone functions. Random Structures Algorithms, 23(3):333–350, 2003. [Wiley:10.1002/rsa.10097].

[25]   E. Mossel, R. O’Donnell, and R. Servedio: Learning functions of k relevant variables. J. Comput. System Sci., 69(3):421–434, 2004. [JCSS:10.1016/j.jcss.2004.04.002].

[26]   M. Naor and O. Reingold: Number-theoretic constructions of efficient pseudo-random functions. J. ACM, 51(2):231–262, 2004. [JACM:10.1145/972639.972643].

[27]   V. A. Nepomnjaščiĭ: Rudimentary predicates and Turing computations (in Russian). Dokl. Akad. Nauk SSSR, 195:282–284, 1970. English translation in Soviet Mathematics Doklady, Vol. 11, pp. 1642–1645, 1970. Math. Reviews MR02811611 (43#7326).

[28]   R. O’Donnell: Hardness amplification within NP. J. Comput. System Sci., 69(1):68–94, 2004. [JCSS:10.1016/j.jcss.2004.01.001].

[29]   R. O’Donnell and R. Servedio: Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844, 2007. [SICOMP:10.1137/060669309].

[30]   A. Razborov: Lower bounds on the monotone network complexity of the logical permanent. Mat. Zametki, 37:887–900, 1985. English translation in Math. Notes of the Academy of Sciences of the USSR, Vol 37, pp. 485-493, 1985.

[31]   R. Servedio: On learning monotone DNF under product distributions. Inform. Comput., 193(1):57–74, 2004.

[32]   É. Tardos: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141–142, 1988. [10.1007BF02122563].

[33]   L. Trevisan: List decoding using the XOR lemma. In Proc. 44th FOCS, pp. 126–135. IEEE Comp. Soc. Press, 2003. [FOCS:10.1109/SFCS.2003.1238187].

[34]   L. G. Valiant: A theory of the learnable. Commun. ACM, 27(11):1134–1142, 1984. [ACM:10.1145/1968.1972].

[35]   L. G. Valiant: Negation is powerless for Boolean slice functions. SIAM J. Comput., 15:531–535, 1986. [SICOMP:10.1137/0215037].

[36]   K. Verbeurgt: Learning DNF under the uniform distribution in quasi-polynomial time. In Proc. 3rd Ann. Workshop Comput. Learn. Theory, pp. 314–326. Morgan Kaufman, 1990.