Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
This work addresses foundational problems in theoretical computer science, such as understanding the relationships between learning, complexity, and randomness, which is significant for researchers in computational complexity and learning theory, though it appears to be incremental in building on existing connections.
The paper tackles the problem of establishing connections between learning algorithms, circuit lower bounds, and pseudorandomness, resulting in multiple new and stronger results, including a generic learning speedup lemma, equivalences between learning models, and consequences for circuit lower bounds.
We prove several results giving new and stronger connections between learning, circuit lower bounds and pseudorandomness. Among other results, we show a generic learning speedup lemma, equivalences between various learning models in the exponential time and subexponential time regimes, a dichotomy between learning and pseudorandomness, consequences of non-trivial learning for circuit lower bounds, Karp-Lipton theorems for probabilistic exponential time, and NC$^1$-hardness for the Minimum Circuit Size Problem.