# Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

arXiv: https://arxiv.org/abs/1602.05161 · HTML: https://mlsanity.com/paper/1602.05161/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2016.

## Built on by (most cited first, 30 of 33)

- [Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Tasks](https://mlsanity.com/paper/2402.04248/) (2024)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Near Optimal Memory-Regret Tradeoff for Online Learning](https://mlsanity.com/paper/2303.01673/) (2023)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [Memory-Sample Lower Bounds for Learning Parity with Noise](https://mlsanity.com/paper/2107.02320/) (2021)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Hardness of Learning Fixed Parities with Neural Networks](https://mlsanity.com/paper/2501.00817/) (2025)
- [The I/O Complexity of Attention, or How Optimal is Flash Attention?](https://mlsanity.com/paper/2402.07443/) (2024)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [Tight Memory-Regret Lower Bounds for Streaming Bandits](https://mlsanity.com/paper/2306.07903/) (2023)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [New constructions of pseudorandom codes](https://mlsanity.com/paper/2409.07580/) (2024)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Estimation of Entropy in Constant Space with Improved Sample Complexity](https://mlsanity.com/paper/2205.09804/) (2022)
- [Impartial Games: A Challenge for Reinforcement Learning](https://mlsanity.com/paper/2205.12787/) (2022)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [On Language Generation in the Limit with Bounded Memory](https://mlsanity.com/paper/2605.30324/) (2026)
- [Tight Time-Space Lower Bounds for Constant-Pass Learning](https://mlsanity.com/paper/2310.08070/) (2023)
- [Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels](https://mlsanity.com/paper/2312.05379/) (2023)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits](https://mlsanity.com/paper/2603.13742/) (2026)

## Abstract (arXiv)

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 parity learning, an unknown string x ∈ 0,1n was chosen uniformly at random. A learner tries to learn x from a stream of samples (a1, b1), (a2, b2) ldots, where each~at is uniformly distributed over 0,1n and bt is the inner product of at and x, modulo~2. We show that any algorithm for parity learning, that uses less than fracn225 bits of memory, requires an exponential number of samples. Previously, there was no non-trivial lower bound on the number of samples needed, for any learning problem, even if the allowed memory size is O(n) (where n is the space needed to store one sample). We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length n, as well as time complexity of n per encryption/decription of each bit, and is provenly and unconditionally secure as long as the attacker uses less than fracn225 memory bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decription.