Publications and Research

Document Type


Publication Date



Over the years a range of positive algorithmic results have been obtained for learning various classes of monotone Boolean functions from uniformly distributed random examples. Prior to our work, however, the only negative result for learning monotone functions in this model has been an information-theoretic lower bound showing that certain super-polynomial-size monotone circuits cannot be learned to accuracy 1/2+w(log n/ p n) (Blum, Burch, and Langford, FOCS’98). This is in contrast with the situation for nonmonotone functions, where a wide range of cryptographic hardness results establish that various “simple” classes of polynomial-size circuits are not learnable by polynomial-time algorithms.

In this paper we establish cryptographic hardness results for learning various “simple” classes of monotone circuits, thus giving a computational analogue of the information-theoretic hardness results of Blum et al. mentioned above. Some of our results show the cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2+1/ p n, which is close to the optimal accuracy bound by positive results of Blum et al. Other results show that under a plausible cryptographic hardness assumption, a class of constant-depth, sub-polynomial-size circuits computing monotone functions is hard to learn. This result is close to optimal in terms of the circuit-size parameter by known positive results as well (Servedio, Information and Computation 2004). Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O’Donnell (JCSS 2004).


This article was originally published in Theory of Computing, available at DOI: 10.4086/toc.2009.v005a013.

This work was distributed under a Creative Commons Attribution License (CC BY 3.0)



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.