TY - CHAP
T1 - Optimal Cryptographic Hardness of Learning Monotone Functions
T2 - Automata, Languages and Programming
Y1 - 2008
A1 - Dana Dachman-Soled
A1 - Lee, Homin K.
A1 - Malkin, Tal
A1 - Servedio, Rocco A.
A1 - Wan, Andrew
A1 - Wee, Hoeteck
ED - Aceto, Luca
ED - Damgård, Ivan
ED - Goldberg, Leslie Ann
ED - Halldórsson, Magnús M.
ED - Ingólfsdóttir, Anna
ED - Walukiewicz, Igor
KW - Data structures
KW - Data Structures, Cryptology and Information Theory
KW - Discrete Mathematics in Computer Science
KW - Numeric Computing
KW - Software Engineering/Programming and Operating Systems
KW - Theory of computation
AB - 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).
JA - Automata, Languages and Programming
T3 - Lecture Notes in Computer Science
PB - Springer Berlin Heidelberg
SN - 978-3-540-70574-1, 978-3-540-70575-8
UR - http://link.springer.com/chapter/10.1007/978-3-540-70575-8_4
ER -