# Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

## Fast learning requires good memory: a time-space lower bound for parity learning

Ran Raz
Weizmann Institute of Science; Visiting Professor, School of Mathematics
March 8, 2016
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, Valiant and Wager and shows that for some learning problems a large storage space is crucial. More formally, in the problem of parity learning, an unknown string $x \in \{0,1\}^n$ was chosen uniformly at random.