Fast learning requires good memory: A time-space lower bound for parity learning

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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 et al. (2016) 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, 1} n was chosen uniformly at random. A learner tries to learn x from a stream of samples (a1,b 1 ), (a2,b 2 ) . . ., where each a t is uniformly distributed over {0, 1} n and b t is the inner product of a t and x, modulo 2. We show that any algorithm for 2 parity learning that uses less than n 25 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/decryption of each bit, and is provably and unconditionally secure as long as the attacker uses less than n 25 memory 2 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/decryption.

Original languageEnglish (US)
Article number3
JournalJournal of the ACM
Volume66
Issue number1
DOIs
StatePublished - Dec 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Bounded storage cryptography
  • Branching program
  • Learning
  • Lower bounds
  • Time-space tradeoff

Fingerprint Dive into the research topics of 'Fast learning requires good memory: A time-space lower bound for parity learning'. Together they form a unique fingerprint.

Cite this