BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Learning algorithms from natural proofs Carmosino, Marco


Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. A natural question is: given that these algorithms are sufficient for circuit lower bounds, to what degree are they necessary? We make progress on this question by showing a generic implication in the opposite direction: from natural proofs of circuit lower bounds (in the sense of Razborov and Rudich) to 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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International