BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Stronger Connections between Learning, Lower Bounds and Pseudorandomness Santhanam, Rahul


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International