{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:45Z","timestamp":1781077785592,"version":"3.54.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T00:00:00Z","timestamp":1544572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1402\/14"],"award-info":[{"award-number":["1402\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fund for Math at IAS"},{"name":"I-CORE Program of the Planning and Budgeting Committee"},{"name":"Simons Collaboration on Algorithms and Geometry"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1412958 and CCF-1714779"],"award-info":[{"award-number":["CCF-1412958 and CCF-1714779"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>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 \u00a0Steinhardt et al. (2016) and shows that for some learning problems, a large storage space is crucial.<\/jats:p>\n                  <jats:p>\n                    More formally, in the problem of parity learning, an unknown string\n                    <jats:italic>x<\/jats:italic>\n                    \u2208 {0,1}\n                    <jats:sup>\n                      <jats:italic>n<\/jats:italic>\n                    <\/jats:sup>\n                    was chosen uniformly at random. A learner tries to learn\n                    <jats:italic>x<\/jats:italic>\n                    from a stream of samples (\n                    <jats:italic>a<\/jats:italic>\n                    <jats:sub>1<\/jats:sub>\n                    ,\n                    <jats:italic>b<\/jats:italic>\n                    <jats:sub>1<\/jats:sub>\n                    ), (\n                    <jats:italic>a<\/jats:italic>\n                    <jats:sub>2<\/jats:sub>\n                    ,\n                    <jats:italic>b<\/jats:italic>\n                    <jats:sub>2<\/jats:sub>\n                    ) \u2026, where each\u00a0\n                    <jats:italic>a<\/jats:italic>\n                    <jats:sub>\n                      <jats:italic>t<\/jats:italic>\n                    <\/jats:sub>\n                    is uniformly distributed over {0,1}\n                    <jats:sup>\n                      <jats:italic>n<\/jats:italic>\n                    <\/jats:sup>\n                    and\n                    <jats:italic>b<\/jats:italic>\n                    <jats:sub>\n                      <jats:italic>t<\/jats:italic>\n                    <\/jats:sub>\n                    is the inner product of\n                    <jats:italic>a<\/jats:italic>\n                    <jats:sub>\n                      <jats:italic>t<\/jats:italic>\n                    <\/jats:sub>\n                    and\n                    <jats:italic>x<\/jats:italic>\n                    , modulo\u00a02. We show that any algorithm for parity learning that uses less than\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    \/25 bits of memory requires an exponential number of samples.\n                  <\/jats:p>\n                  <jats:p>\n                    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\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ) (where\n                    <jats:italic>n<\/jats:italic>\n                    is the space needed to store one sample).\n                  <\/jats:p>\n                  <jats:p>\n                    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                    <jats:italic>n<\/jats:italic>\n                    , as well as time complexity of\n                    <jats:italic>n<\/jats:italic>\n                    per encryption\/decryption of each bit, and is provably and unconditionally secure as long as the attacker uses less than\n                    <jats:italic>n<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    \/25 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\/decryption.\n                  <\/jats:p>","DOI":"10.1145\/3186563","type":"journal-article","created":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T07:49:32Z","timestamp":1544600972000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Fast Learning Requires Good Memory"],"prefix":"10.1145","volume":"66","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301424"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai. 1999b. A non-linear time lower bound for boolean branching programs. In FOCS. 60--70. Mikl\u00f3s Ajtai. 1999b. A non-linear time lower bound for boolean branching programs. In FOCS. 60--70.","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1003845"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Yonatan Aumann and Michael O. Rabin. 1999. Information theoretically secure communication in the limited storage space model. In CRYPTO. 65--79. Yonatan Aumann and Michael O. Rabin. 1999. Information theoretically secure communication in the limited storage space model. In CRYPTO. 65--79.","DOI":"10.1007\/3-540-48405-1_5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_2_1_6_1","unstructured":"Paul Beame Shayan Oveis Gharan and Xin Yang. 2018. Time-space tradeoffs for learning finite functions from random evaluations with applications to polynomials. In COLT. 843--856. (also in Electronic Colloquium on Computational Complexity (ECCC) 24: 120 (2017)) Paul Beame Shayan Oveis Gharan and Xin Yang. 2018. Time-space tradeoffs for learning finite functions from random evaluations with applications to polynomials. In COLT. 843--856. (also in Electronic Colloquium on Computational Complexity (ECCC) 24: 120 (2017))"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1778"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636867"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Christian Cachin and Ueli M. Maurer. 1997. Unconditional security against memory-bounded adversaries. In CRYPTO. 292--306. Christian Cachin and Ueli M. Maurer. 1997. Unconditional security against memory-bounded adversaries. In CRYPTO. 292--306.","DOI":"10.1007\/BFb0052243"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Stefan Dziembowski and Ueli M. Maurer. 2004. On generating the initial key in the bounded-storage model. In EUROCRYPT. 126--137. Stefan Dziembowski and Ueli M. Maurer. 2004. On generating the initial key in the bounded-storage model. In EUROCRYPT. 126--137.","DOI":"10.1007\/978-3-540-24676-3_8"},{"key":"e_1_2_1_11_1","unstructured":"Yuval Dagan and Ohad Shamir. 2018. Detecting correlations with little memory and communication. COLT (2018) 1145--1198. Yuval Dagan and Ohad Shamir. 2018. Detecting correlations with little memory and communication. COLT (2018) 1145--1198."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1671"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101822"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188962"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055430"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/146395.146399"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000012"},{"key":"e_1_2_1_18_1","unstructured":"Dana Moshkovitz and Michal Moshkovitz. 2017. Mixing implies lower bounds for space bounded learning. In COLT. 1516--1566. (also in Electronic Colloquium on Computational Complexity (ECCC) 24: 17 (2017)) Dana Moshkovitz and Michal Moshkovitz. 2017. Mixing implies lower bounds for space bounded learning. In COLT. 1516--1566. (also in Electronic Colloquium on Computational Complexity (ECCC) 24: 17 (2017))"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Entropy samplers and strong generic lower bounds for space bounded learning","volume":"28","author":"Moshkovitz Dana","year":"2018","journal-title":"ITCS."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Ran Raz. 2016. Fast learning requires good memory: A time-space lower bound for parity learning. In FOCS. 266--275. Ran Raz. 2016. Fast learning requires good memory: A time-space lower bound for parity learning. In FOCS. 266--275.","DOI":"10.1109\/FOCS.2016.36"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Ran Raz. 2017. A time-space lower bound for a large class of learning problems. In FOCS. 732--742. (also in Electronic Colloquium on Computational Complexity (ECCC) 24: 20 (2017)) Ran Raz. 2017. A time-space lower bound for a large class of learning problems. In FOCS. 732--742. (also in Electronic Colloquium on Computational Complexity (ECCC) 24: 20 (2017))","DOI":"10.1109\/FOCS.2017.73"},{"key":"e_1_2_1_22_1","unstructured":"Ohad Shamir. 2014. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In NIPS. 163--171. Ohad Shamir. 2014. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In NIPS. 163--171."},{"key":"e_1_2_1_23_1","unstructured":"Jacob Steinhardt Gregory Valiant and Stefan Wager. 2016. Memory communication and statistical queries. In COLT. 1490--1516. (also in Electronic Colloquium on Computational Complexity (ECCC) 22: 126 (2015)) Jacob Steinhardt Gregory Valiant and Stefan Wager. 2016. Memory communication and statistical queries. In COLT. 1490--1516. (also in Electronic Colloquium on Computational Complexity (ECCC) 22: 126 (2015))"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-003-0237-x"},{"key":"e_1_2_1_25_1","first-page":"78","article-title":"Information theoretically secure databases","volume":"23","author":"Valiant Gregory","year":"2016","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0221-1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.34"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186563","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186563","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T11:48:50Z","timestamp":1775303330000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186563"}},"subtitle":["A Time-Space Lower Bound for Parity Learning"],"short-title":[],"issued":{"date-parts":[[2018,12,12]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3186563"],"URL":"https:\/\/doi.org\/10.1145\/3186563","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,12]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}