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 ... more >>>

We define a concept class {\cal F} to be time-space hard (or memory-samples hard) if any learning algorithm for {\cal F} requires either a memory of size super-linear in n or a number of samples super-polynomial in n, where n is the length of one sample.

A recent work shows ... more >>>