Open Collections

Learning algorithms from natural proofs

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: UCSD

2017-03-10

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/60853

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/