Abstract
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 s(n).
We show: Learning Speedups. If C[poly(n)] admits a randomized weak learning algorithm under the uniform distribution with membership queries that runs in time 2n/n!(1), then for every k 1 and ϵ > 0 the class C[nk] can be learned to high accuracy in time O(2nϵ ).
There is ϵ > 0 such that C[2nϵ ] can be learned in time 2n/n!(1) if and only if C[poly(n)] 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[poly(n)] if and only if there are no exponentially secure pseudorandom functions computable in C[poly(n)]. Lower Bounds from Nontrivial Learning.
If for each k 1, (depth-d)-C[nk] admits a randomized weak learning algorithm with membership queries under the uniform distribution that runs in time 2n/n!(1), then for each k 1, BPE (depth-d)-C[nk]. If for some ϵ > 0 there are P-natural proofs useful against C[2nϵ ], then ZPEXP C[poly(n)].
Karp-Lipton Theorems for Probabilistic Classes. If there is a k > 0 such that BPE i.o.Circuit[nk], then BPEXP i.o.EXP/O(log n).
If ZPEXP i.o.Circuit[2n/3], then ZPEXP i.o.ESUBEXP. Hardness Results for MCSP.
All functions in non-uniform NC1 reduce to the Minimum Circuit Size Problem via truth-table reductions computable by TC0 circuits. In particular, if MCSP 2 TC0 then NC1 = TC0. (C) Igor C.
Oliveira and Rahul Santhanam.