Stronger Connections between Learning, Lower Bounds and Pseudorandomness

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness, including: 1. (Learning Speedups) Let C be any "typical" class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). If C[poly] admits a randomized weak learning algorithm under the uniform distribution with membership queries that runs in time 2^n/n^{\omega(1)}, then for every k and \varepsilon > 0 the class C[n^k] can be learned to high accuracy in time O(2^{n^\varepsilon}). 2.(Equivalences) There is \varepsilon > 0 such that C[2^{n^{\varepsilon}}] can be learned in time 2^n/n^{\omega(1)} if and only if C[poly] can be learned in time 2^{O((\log n)^c)}. Furthermore, our proof technique yields equivalences between various randomized learning models in the exponential and sub-exponential time settings, such as learning with membership queries, learning with membership and equivalence queries, and the related framework of truth-table compression. 3.(Learning versus Pseudorandom Functions) In the non-uniform setting, there is non-trivial learning for C[poly(n)] if and only if there are no secure pseudorandom function families computable in C[poly]. 4.(Lower Bounds from Nontrivial Learning Algorithms) Let C be any class of Boolean circuits closed under projection. If for each k, C[n^k] admits a randomized weak learning algorithm with membership queries under the uniform distribution that runs in time 2^n/n^{\omega(1)}, then for each k, BPE is not contained in C[n^k]. If there are P-natural proofs useful against C[2^{n^{o(1)}}], then ZPEXP is not contained in C[poly]. Among the proof techniques we use are the uniform hardness-randomness tradeoffs of [Impagliazzo-Wigderson, Trevisan-Vadhan], the easy witness method of [Kabanets, Impagliazzo-Kabanets-Wigderson], the interpretation of the Nisan-Wigderson generator as a pseudo-random function generator due to [Carmosino-Impagliazzo-Kabanets-Kolokolova] and the approximate min-max theorem of [Althofer, Lipton-Young]. This is joint work with Igor Carboni Oliveira.Non UBCUnreviewedAuthor affiliation: University of OxfordFacult