We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:
Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform distribution with membership queries that runs in time $2^n/n^{\omega(1)}$, then for each $k \geq 1$ and $\varepsilon > 0$ the class C[$n^k$] can be learned to high accuracy in time $O(2^{n^\varepsilon})$. 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[$n^{O(1)}$] can be learned in time $2^{(log n)^{O(1)}}$
Equivalences between Learning Models: We use learning speedups to obtain equivalences between various randomized learning and compression models, including sub-exponential time learning with membership queries, sub-exponential time learning with membership and equivalence queries, probabilistic function compression and probabilistic average-case function compression.
A Dichotomy between Learnability and Pseudorandomness: In the non-uniform setting, there is non-trivial learning for C[$n^{O(1)}$] if and only if there are no exponentially secure pseudorandom functions computable in C[$n^{O(1)}$].
Lower Bounds from Nontrivial Learning: If for each k >= 1, (depth-$d$)-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 \geq 1$, BPE is not contained in (depth-$d$)-C[$n^k$]. If for some $\varepsilon > 0$ there are P-natural proofs useful against C[$2^{n^{\varepsilon}}$], then ZPEXP is not contained in C[$n^{O(1)}$].
Karp-Lipton Theorems for Probabilistic Classes: If there is a $k > 0$ such that BPE is contained in i.o.Circuit[$n^k$], then BPEXP is contained in i.o.EXP/O(log(n)). If ZPEXP is contained in i.o.Circuit[$2^{n/3}$], then ZPEXP is contained in i.o.ESUBEXP.
Hardness Results for MCSP: All functions in non-uniform NC^1 reduce to the Minimum Circuit Size Problem via truth-table reductions computable by TC^0 circuits. In particular, if MCSP in TC^0 then NC^1 = TC^0.
