Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-008 | 26th January 2016 23:46

Algorithms from Natural Lower Bounds



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 $AC^0[p]$ circuits (due to Razborov and Smolensky) to get the first quasi-polynomial time algorithm for learning $AC^0[p]$ functions, in the PAC model over the uniform distribution, with membership queries.

ISSN 1433-8092 | Imprint