Paper Info
Title
Algorithms from Natural Lower Bounds.
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 AC[p] circuits (due to Razborov and Smolensky) to get the first quasi-polynomial time algorithm for learning AC[p] functions, in the PAC model over the uniform distribution, with membership queries. ∗This work was partially supported by the Simons Foundation and NSF grants #CNS-1523467 and CCF-121351 (M. Carmosino, R. Impagliazzo) and by NSERC Discovery grants (V. Kabanets, A. Kolokolova). This work was done in part while all authors were visiting Simons Institute for the Theory of Computing. †Department of Computer Science, University of California San Diego, La Jolla, CA; mcarmosi@eng.ucsd.edu ‡Department of Computer Science, University of California San Diego, La Jolla, CA; russell@cs.ucsd.edu §School of Computing Science, Simon Fraser University, Burnaby, BC, Canada; kabanets@cs.sfu.ca ¶Department of Computer Science, Memorial University of Newfoundland, St. John’s, NL, Canada; kol@mun.ca
Year
Venue
Field
2016
Electronic Colloquium on Computational Complexity (ECCC)
Discrete mathematics,Combinatorics,Theory of computing,Algorithm,Network analysis,Data compression,Mathematics
DocType
Volume
Citations 
Journal
23
0
PageRank 
References 
Authors
0.34
16
4
Name
Order
Citations
PageRank
Marco L. Carmosino100.34
Russell Impagliazzo25444482.13
Valentine Kabanets356235.38
Antonina Kolokolova45010.09