Seminars & Colloquia Calendar
Time-Space Hardness of Learning Sparse Parities
Avishay Tal: IAS
Location: CoRE 301
Date & time: Wednesday, 01 March 2017 at 11:00AM - 11:11AM
One approach is to gather \[O(n)\]random examples and perform Gaussian-elimination. This requires a memory of size \[O(n^2)\]and \[poly(n)\]time. Another approach is to go over all possible \[2^n\]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(2^n * n)\]time.
In a recent work, Raz [FOCS, 2016] shows that if an algorithm has memory of size much smaller than \[n^2\], then it has to spend exponential 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 formulae, linear-size decision trees, and logarithmic-size juntas are all time-space hard.
Based on joint work with Gillat Kol and Ran Raz.