Theory Seminar

Friday, November 4, 2016 - 2:30pm


Traffic21 Classroom 6501 Gates & Hillman Centers


AVISHAY TAL, Postdoctoral Researcher

How can one learn a parity function, i.e., a function of the form f(x) = a_1 x_1 + a_2 x_2 + ... + a_n x_n (mod 2) where a_1, ..., a_n are in {0,1}, from random examples? One approach is to gather O(n) random examples and perform Gaussian-elimination. This requires a memory of size O(n2) and poly(n) time. Another approach is to go over all possible 2n parity functions and to verify them by checking O(n) random examples for each guess. This requires a memory of size O(n), but O(2n * n) time. In a recent work, Raz [FOCS, 2016] shows that if an algorithm has memory of size much smaller than n2, then it has to spend roughly 2n time in order to learn a parity function. In other words, fast learning requires good memory. In this work, we show that even if the parity function is known to be extremely sparse, where only log(n) of the a_i's are nonzero, then the learning task is still time-space hard. That is, we show that any algorithm with linear size memory and polynomial time fails to learn log(n)-sparse parities. Consequently, the classical tasks of learning linear-size DNF Formulas, linear-size Decision Trees and logarithmic-size Juntas are all time-space hard. Based on joint work with Gillat Kol and Ran Raz.

Event Website:

For More Information, Contact:


Seminar Series