Learning algorithms from circuit lower bounds

Abstract We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small circuits attempting to compute hard functions. As our main result, we prove that if it is possible to find efficiently, in a particular interactive way, errors of many $$p$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> -size circuits attempting to solve hard problems, then $$p$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>p</mml:mi> </mml:math> -size circuits can be PAC learned over the uniform distribution with membership queries by circuits of subexponential size. The opposite implication holds as well. This provides a new characterization of learning algorithms and the natural proofs barrier of Razborov and Rudich. The proof is based on a method of reconstructing Nisan-Wigderson generators introduced by Krajíček (2010) and used to analyze complexity of circuit lower bounds in bounded arithmetic. An interesting consequence of known constructions of learning algorithms from circuit lower bounds is a learning speedup of Oliveira and Santhanam (2016). We present an alternative proof of this phenomenon and discuss its potential to advance the program of hardness magnification.