Algorithms from Natural Lower Bounds.

摘要: Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply lower bounds. We show a generic implication in the opposite direction: natural properties (in sense of Razborov Rudich) randomized learning algorithms. This is first outside derandomization setting. As an application, we use known bounds for AC[p] circuits (due to Smolensky) get quasi-polynomial time algorithm functions, PAC model over uniform distribution, with membership queries. ∗This work was partially supported by Simons Foundation NSF grants #CNS-1523467 CCF-121351 (M. Carmosino, R. Impagliazzo) NSERC Discovery (V. Kabanets, A. Kolokolova). done part while all authors were visiting Institute Theory Computing. †Department Computer Science, University California San Diego, La Jolla, CA; mcarmosi@eng.ucsd.edu ‡Department russell@cs.ucsd.edu §School Computing Simon Fraser University, Burnaby, BC, Canada; kabanets@cs.sfu.ca ¶Department Memorial Newfoundland, St. John’s, NL, kol@mun.ca