Fetching the paper…
Reading the bibliography…
We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior work.
Linear Groups with an Exposition of the Galois Field Theory
Leonard E. Dickson · 1901
Earlier work this paper cites.
Weight distributions of Bose-Chaudhuri-Hocquenghem codes
Tadao Kasami · 1966
Earlier work this paper cites.
Linear recurring sequences over finite fields
Robert James McEliece · 1967
Earlier work this paper cites.
Algebraic Coding Theory
Elwyn R Berlekamp · 1968
Earlier work this paper cites.
Weight enumerator for second-order Reed-Muller codes
Neil J. A. Sloane and Elwyn R. Berlekamp · 1970
Earlier work this paper cites.
Random low-degree polynomials are hard to approximate
Ido Ben-Eliezer, Rani Hod, and Shachar Lovett · 2012
Earlier work this paper cites.
Weight distribution and list-decoding size of Reed-Muller codes
Tali Kaufman, Shachar Lovett, and Ely Porat · 2012
Cited alongside, same era.
Fundamental limits of online and distributed algorithms for statistical learning and estimation
Ohad Shamir · 2014
Cited alongside, same era.
Abhishek Bhowmick and Shachar Lovett · 2015
Cited alongside, same era.
The list decoding radius of reed-muller codes over small fields
Abhishek Bhowmick and Shachar Lovett · 2015
Cited alongside, same era.
Time-space hardness of learning sparse parities
Gillat Kol, Ran Raz, and Avishay Tal · 2016
Cited alongside, same era.
Fast learning requires good memory: A time-space lower bound for parity learning
Ran Raz · 2016
Memory, communication, and statistical queries
Jacob Steinhardt, Gregory Valiant, and Stefan Wager · 2016
Later among the works it cites.
Extractor-based time-space tradeoffs for learning
Sumegha Garg, Ran Raz, and Avishay Tal · 2017
Closest in time.
Mixing implies lower bounds for space bounded learning
Michal Moshkovitz and Dana Moshkovitz · 2017
Closest in time.
Mixing implies strong lower bounds for space bounded learning
Michal Moshkovitz and Dana Moshkovitz · 2017
Closest in time.
A time-space lower bound for a large class of learning problems
Ran Raz · 2017
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.