TY - JOUR

T1 - Fast learning requires good memory

T2 - A time-space lower bound for parity learning

AU - Raz, Ran

N1 - Funding Information:
A preliminary version of the article appeared at the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016) (Raz 2016). Research supported by the Israel Science Foundation grant No. 1402/14, by the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation, by the Simons Collaboration on Algorithms and Geometry, by the Fund for Math at IAS, and by the National Science Foundation grants No. CCF-1412958 and CCF-1714779. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation. Authors’ address: R. Raz, Department of Computer Science, Princeton University, 35 Olden Street, Princeton, NJ 08540, USA; email: ran.raz.mail@gmail.com. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2018 Association for Computing Machinery. 0004-5411/2018/12-ART3 $15.00 https://doi.org/10.1145/3186563
Publisher Copyright:
© 2018 Association for Computing Machinery.

PY - 2018/12

Y1 - 2018/12

N2 - 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.

AB - 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.

KW - Bounded storage cryptography

KW - Branching program

KW - Learning

KW - Lower bounds

KW - Time-space tradeoff

UR - http://www.scopus.com/inward/record.url?scp=85058820561&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85058820561&partnerID=8YFLogxK

U2 - 10.1145/3186563

DO - 10.1145/3186563

M3 - Article

AN - SCOPUS:85058820561

VL - 66

JO - Journal of the ACM

JF - Journal of the ACM

SN - 0004-5411

IS - 1

M1 - 3

ER -