Extractor-Based Time-Space Lower Bounds for Learning

Ronald Graham, Joel Spencer: A Constructive Solution to a Tournament Problem. Canad. Math. Bull. 14: 45-48 (1971)

1971

Earlier work this paper cites.

Miklos Santha, Umesh V. Vazirani: Generating Quasi-Random Sequences from Slightly-Random Sources. FOCS 1984: 434-440

1984

Earlier work this paper cites.

Benny Chor, Oded Goldreich: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. Comput. 17(2): 230-261 (1988)

1988

Earlier work this paper cites.

Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, Steven Rudich: Weakly learning DNF and characterizing statistical query learning using Fourier analysis. STOC 1994: 253-262

1994

Earlier work this paper cites.

Noga Alon: Tools from Higher Algebra. In Handbook of Combinatorics, R.L.Graham, M.Grotschel and L.Lovasz, eds, North Holland (1995), Chapter 32: 1749-1783

1995

Earlier work this paper cites.

Michael J. Kearns: Efficient Noise-Tolerant Learning from Statistical Queries. J. ACM 45(6): 983-1006 (1998)

1998

Earlier work this paper cites.

Ran Raz: Extractors with weak random seeds. STOC 2005: 11-20

2005

Earlier work this paper cites.

Yonatan Bilu, Nathan Linial: Lifts, Discrepancy and Nearly Optimal Spectral Gap. Combinatorica 26(5): 495-519 (2006)

2006

Cited alongside, same era.

Ido Ben-Eliezer, Rani Hod, Shachar Lovett: Random low-degree polynomials are hard to approximate. Computational Complexity, 21(1): 63–81 (2012)

2012

Cited alongside, same era.

Gillat Kol, Ran Raz: Interactive channel capacity. STOC 2013: 715-724

2013

Cited alongside, same era.

Ohad Shamir: Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation. NIPS 2014: 163-171

2014

Cited alongside, same era.

Ran Raz: Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. FOCS 2016: 266-275

2016

Cited alongside, same era.

Paul Beame, Shayan Oveis Gharan, Xin Yang: Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. Manuscript (2017)

2017

Closest in time.

Gillat Kol, Ran Raz, Avishay Tal: Time-Space Hardness of Learning Sparse Parities. STOC 2017: 1067-1080

2017

Closest in time.

Dana Moshkovitz, Michal Moshkovitz: Mixing Implies Lower Bounds for Space Bounded Learning. Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1516-1566, 2017. Also in: Electronic Colloquium on Computational Complexity (ECCC) 24: 17 (2017)

2017

Closest in time.

Dana Moshkovitz, Michal Moshkovitz: Mixing Implies Strong Lower Bounds for Space Bounded Learning. Electronic Colloquium on Computational Complexity (ECCC) 24: 116 (2017)

2017

Closest in time.

Michal Moshkovitz, Naftali Tishby: Mixing Complexity and its Applications to Neural Networks. CoRR abs/1703.00729 (2017)