Constructing hard functions from learning algorithms

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class C subset of P/poly of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then EXPNP not subset of C (the class EXPNP was subsequently improved to EXP by Hitchcock and Harkins). In this paper, we improve on these results and show If C is exactly learnable with membership and equivalence queries in polynomial-time, then DTIME(n(omega(1))) not subset of C. We obtain even stronger consequences if the class C is learnable in the mistake-bounded model, in which case we prove an average-case hardness result against C. If C is learnable in polynomial time in the PAC model then PSPACE not subset of C, unless PSPACE not subset of BPP. Removing this extra assumption from the statement of the theorem would provide an unconditional proof that PSPACE not subset of BPP. If C is efficiently learnable in the Correlational Statistical Query (CSQ) model, we show that there exists an explicit function f that is average-case hard for circuits in C. To the best of our knowledge, this result provides stronger average-case hardness guarantees than those obtained by SQ-dimension arguments (Blum et al. 1993). We also obtain a non-constructive extension of this result to the stronger Statistical Query (SQ) model. Similar results hold when the learning algorithm runs in subexponential time. Our proofs regarding exact and mistake-bounded learning are simple and self-contained, yield explicit hard functions, and show how to use mistake-bounded learners to "diagonalize" over families of polynomial-size circuits. Our consequences for PAC learning lead to new proofs of Karp-Lipton-style collapse results, and the lower bounds from SQ learning make use of recent work relating combinatorial discrepancy to the existence of hard-onaverage functions.