# Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

arXiv: https://arxiv.org/abs/1611.01190 · HTML: https://mlsanity.com/paper/1611.01190/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2016.

## Built on by (most cited first, 3 of 3)

- [Learning with distributional inverters](https://mlsanity.com/paper/2112.12340/) (2021)
- [Learning algorithms versus automatability of Frege systems](https://mlsanity.com/paper/2111.10626/) (2021)
- [Agnostic Membership Query Learning with Nontrivial Savings: New Results, Techniques](https://mlsanity.com/paper/2311.06690/) (2023)

## Abstract (arXiv)

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 NC1-hardness for the Minimum Circuit Size Problem.