Pseudorandomness Seminar

Learning algorithms for circuit complexity classes are often obtained by inspecting the proofs of circuit lower bounds. In recent work (CIKK16), it was show that this observation is somewhat generic: for sufficiently expressive circuit classes C, a natural proof (in the sense of Razborov-Rudich 97) of a circuit lower bound against C implies a learning algorithm for concepts exactly realizable by C-circuits. The learning algorithm constructed in CIKK16 does not need to "inspect" the proof of the bound: it only requires that the proof is natural. In this talk we present the natural learning technique, which is an application of algorithms from the crypto/derandomization literature. Then we discuss an extension of the technique to learning concepts only approximately realizable by C-circuits (agnostic learning).
This is joint work with Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova.