# Optimal Cryptographic Hardness of Learning Monotone Functions

 Title Optimal Cryptographic Hardness of Learning Monotone Functions Publication Type Book Chapters Year of Publication 2008 Authors Dachman-Soled D, Lee HK, Malkin T, Servedio RA, Wan A, Wee H Editor Aceto L, Damgård I, Goldberg LAnn, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I Book Title Automata, Languages and Programming Series Title Lecture Notes in Computer Science Pagination 36 - 47 Publisher Springer Berlin Heidelberg ISBN Number 978-3-540-70574-1, 978-3-540-70575-8 Keywords Data structures, Data Structures, Cryptology and Information Theory, Discrete Mathematics in Computer Science, Numeric Computing, Software Engineering/Programming and Operating Systems, Theory of computation Abstract A wide range of positive and negative results have been established for learning different classes of Boolean functions from uniformly distributed random examples. However, polynomial-time algorithms have thus far been obtained almost exclusively for various classes of monotone functions, while the computational hardness results obtained to date have all been for various classes of general (nonmonotone) functions. Motivated by this disparity between known positive results (for monotone functions) and negative results (for nonmonotone functions), we establish strong computational limitations on the efficient learnability of various classes of monotone functions. We give several such hardness results which are provably almost optimal since they nearly match known positive results. Some of our results show cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2+1/n‾‾√1/2 + 1/\sqrt{n} ; this accuracy bound is close to optimal by known positive results (Blum et al., FOCS ’98). 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 ’04). Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O’Donnell (JCSS ’04). URL http://link.springer.com/chapter/10.1007/978-3-540-70575-8_4