"Learning Algorithms from Natural Proofs"
Marco Carmosino
(UCSD)
Monday, April 11th, 2016, 2:00 pm
EBU3B, Room 4258
Abstract:
Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization setting. As an application, we use known natural lower bounds for AC0[p] circuits (due to Razborov and Smolensky) to get the first quasi-polynomial time algorithm for learning AC0[p] functions, in the PAC model over the uniform distribution, with membership queries.
Joint work with Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova.
Link to paper (to appear in CCC 2016) http://eccc.hpi-web.de/report/2016/008/