{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:44:06Z","timestamp":1787017446617,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Collaboration on Algorithms and Geometry, Simons Investigator Award"],"award-info":[{"award-number":["Collaboration on Algorithms and Geometry, Simons Investigator Award"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["RI-1816753, CAREER CIF 1845360, CCF-1814524"],"award-info":[{"award-number":["RI-1816753, CAREER CIF 1845360, CCF-1814524"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451000","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"694-707","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Continuous LWE"],"prefix":"10.1145","author":[{"given":"Joan","family":"Bruna","sequence":"first","affiliation":[{"name":"New York University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8616-3163","authenticated-orcid":false,"given":"Oded","family":"Regev","sequence":"additional","affiliation":[{"name":"New York University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3033-906X","authenticated-orcid":false,"given":"Min Jae","family":"Song","sequence":"additional","affiliation":[{"name":"New York University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Mikl\u00f3s Ajtai and Cynthia Dwork. 1997. A public-key cryptosystem with worst-case\/average-case equivalence. In STOC. Pages 284\u2013293. isbn:0897918886 https:\/\/doi.org\/10.1145\/258533.258604 10.1145\/258533.258604","DOI":"10.1145\/258533.258604"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Rong Ge. 2011. New algorithms for learning in presence of errors. In ICALP. Pages 403\u2013415.","DOI":"10.1007\/978-3-642-22006-7_34"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000512"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579403"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski Adeline Langlois Chris Peikert Oded Regev and Damien Stehl\u00e9. 2013. Classical hardness of learning with errors. In STOC. Pages 575\u2013584. https:\/\/doi.org\/10.1145\/2488608.2488680 10.1145\/2488608.2488680","DOI":"10.1145\/2488608.2488680"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Spencer Charles Brubaker and Santosh Vempala. 2008. Isotropic PCA and affine-invariant clustering. In FOCS. Pages 551\u2013560. https:\/\/doi.org\/10.1109\/FOCS.2008.48 10.1109\/FOCS.2008.48","DOI":"10.1109\/FOCS.2008.48"},{"key":"e_1_3_2_1_8_1","first-page":"831","article-title":"Adversarial examples from computational constraints","author":"Bubeck Sebastien","year":"2019","unstructured":"Sebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. 2019. Adversarial examples from computational constraints. In ICML. 97, Pages 831\u2013840.","journal-title":"ICML. 97, Pages"},{"key":"e_1_3_2_1_9_1","unstructured":"Sanjoy Dasgupta. 1999. Learning mixtures of Gaussians. In FOCS. Pages 634. isbn:0769504094"},{"key":"e_1_3_2_1_10_1","first-page":"2007","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical Gaussians","volume":"8","author":"Dasgupta Sanjoy","year":"2007","unstructured":"Sanjoy Dasgupta and Leonard Schulman. 2007. A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. JMLR, 8, 2007. Pages 203\u2013226. issn:1532-4435","journal-title":"JMLR"},{"key":"e_1_3_2_1_11_1","unstructured":"Luc Devroye Abbas Mehrabian and Tommy Reddad. 2018. The total variation distance between high-dimensional Gaussians."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1201\/b19567-21"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Ilias Diakonikolas Daniel M. Kane and Alistair Stewart. 2017. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In FOCS. Pages 73\u201384. https:\/\/doi.org\/10.1109\/FOCS.2017.16 10.1109\/FOCS.2017.16","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Ilias Diakonikolas Daniel M. Kane and Alistair Stewart. 2018. List-decodable robust mean estimation and learning mixtures of spherical Gaussians. In STOC. Pages 1047\u20131060. https:\/\/doi.org\/10.1145\/3188745.3188758 10.1145\/3188745.3188758","DOI":"10.1145\/3188745.3188758"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_17_1","unstructured":"Sushrut Karmalkar Adam Klivans and Pravesh Kothari. 2019. List-decodable linear regression. In NeurIPS. Pages 7425\u20137434."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Pravesh K. Kothari Jacob Steinhardt and David Steurer. 2018. Robust moment estimation and improved clustering via sum of squares. In STOC. Pages 1035\u20131046. https:\/\/doi.org\/10.1145\/3188745.3188970 10.1145\/3188745.3188970","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Vadim Lyubashevsky and Daniele Micciancio. 2009. On bounded distance decoding unique shortest vectors and the minimum distance problem. In CRYPTO. Pages 577\u2013594. https:\/\/doi.org\/10.1007\/978-3-642-03356-8_34 10.1007\/978-3-642-03356-8_34","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Daniele Micciancio and Chris Peikert. 2012. Trapdoors for lattices: simpler tighter faster smaller. In EUROCRYPT. Pages 700\u2013718. https:\/\/doi.org\/10.1007\/978-3-642-29011-4_41 10.1007\/978-3-642-29011-4_41","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"e_1_3_2_1_24_1","unstructured":"Hermann Minkowski. 1910. Geometrie der Zahlen. B.G. Teubner."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316882177"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Ankur Moitra and Gregory Valiant. 2010. Settling the polynomial learnability of mixtures of Gaussians. In FOCS. Pages 93\u2013102. https:\/\/doi.org\/10.1109\/FOCS.2010.15 10.1109\/FOCS.2010.15","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_1_27_1","first-page":"1894","article-title":"Contributions to the mathematical theory of evolution","volume":"185","author":"Pearson Karl","year":"1894","unstructured":"Karl Pearson. 1894. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185, 1894. Pages 71\u2013110.","journal-title":"Philosophical Transactions of the Royal Society of London. A"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Chris Peikert. 2010. An efficient and parallel Gaussian sampler for lattices. In CRYPTO. Pages 80\u201397.","DOI":"10.1007\/978-3-642-14623-7_5"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000074"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Chris Peikert Oded Regev and Noah Stephens-Davidowitz. 2017. Pseudorandomness of ring-LWE for any ring and modulus. In STOC. Pages 461\u2013473. isbn:9781450345286 https:\/\/doi.org\/10.1145\/3055399.3055489 10.1145\/3055399.3055489","DOI":"10.1145\/3055399.3055489"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Prasad Raghavendra and Morris Yau. 2020. List decodable learning via sum of squares. In SODA. Pages 161\u2013180.","DOI":"10.1137\/1.9781611975994.10"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039490"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Oded Regev. 2005. On lattices learning with errors random linear codes and cryptography. In STOC. Pages 84\u201393. isbn:1-58113-960-8 https:\/\/doi.org\/10.1145\/1060590.1060603 10.1145\/1060590.1060603","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Oded Regev and Aravindan Vijayaraghavan. 2017. On learning mixtures of well-separated Gaussians. In FOCS. Pages 85\u201396. https:\/\/doi.org\/10.1109\/FOCS.2017.17 10.1109\/FOCS.2017.17","DOI":"10.1109\/FOCS.2017.17"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20247"},{"key":"e_1_3_2_1_36_1","unstructured":"Christian Szegedy Wojciech Zaremba Ilya Sutskever Joan Bruna Dumitru Erhan Ian Goodfellow and Rob Fergus. 2014. Intriguing properties of neural networks. In ICLR. arxiv:1312.6199"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Santosh Vempala and Grant Wang. 2002. A spectral algorithm for learning mixtures of distributions. In FOCS. Pages 113.","DOI":"10.1109\/SFCS.2002.1181888"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451000","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451000","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451000","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:01:44Z","timestamp":1750183304000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451000"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":38,"alternative-id":["10.1145\/3406325.3451000","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451000","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}