Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

Ran Raz

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Val…