{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:22:56Z","timestamp":1778127776149,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CNS-2154149, CCF-1940205"],"award-info":[{"award-number":["CNS-2154149, CCF-1940205"]}]},{"name":"European Union?s Horizon research and innovation programme","award":["815464"],"award-info":[{"award-number":["815464"]}]},{"name":"Siebel Scholars Foundation","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718284","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1910-1920","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7131-956X","authenticated-orcid":false,"given":"Kiril","family":"Bangachev","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6716-8827","authenticated-orcid":false,"given":"Guy","family":"Bresler","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9719-0036","authenticated-orcid":false,"given":"Stefan","family":"Tiegel","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2666-0045","authenticated-orcid":false,"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450524"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2211.11693"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746606"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.48"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_25"},{"key":"e_1_3_2_1_8_1","unstructured":"Abhishek Banerjee Chris Peikert and Alon Rosen. 2011. Pseudorandom Functions and Lattices. Cryptology ePrint Archive Paper 2011\/401. https:\/\/eprint.iacr.org\/2011\/401"},{"key":"e_1_3_2_1_9_1","unstructured":"Kiril Bangachev Guy Bresler Stefan Tiegel and Vinod Vaikuntanathan. 2024. Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations. arxiv:2411.12512. arxiv:2411.12512"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 36th International Conference on Neural Information Processing Systems. Curran Associates Inc.","author":"Barak Boaz","year":"2024","unstructured":"Boaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. 2024. Hidden progress in deep learning: SGD learns parities near the computational limit. In Proceedings of the 36th International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA. Article 1581, 15 pages. isbn:9781713871088 https:\/\/openreview.net\/forum?id=8XWP2ewX-im"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_12_1","volume-title":"29th Annual Conference on Learning Theory, Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.) (Proceedings of Machine Learning Research","volume":"445","author":"Barak Boaz","year":"2016","unstructured":"Boaz Barak and Ankur Moitra. 2016. Noisy Tensor Completion via the Sum-of-Squares Hierarchy. In 29th Annual Conference on Learning Theory, Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.) (Proceedings of Machine Learning Research, Vol. 49). PMLR, Columbia University, New York, New York, USA. 417\u2013445. https:\/\/proceedings.mlr.press\/v49\/barak16.html"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_23"},{"key":"e_1_3_2_1_15_1","unstructured":"Zvika Brakerski Noah Stephens-Davidowitz and Vinod Vaikuntanathan. 2020. On the Hardness of Average-case k-SUM. arxiv:2010.08821."},{"key":"e_1_3_2_1_16_1","unstructured":"Dung Bui Geoffroy Couteau and Nikolas Melissaris. 2024. Structured-Seed Local Pseudorandom Generators and their Applications. Cryptology ePrint Archive https:\/\/eprint.iacr.org\/2024\/1027"},{"key":"e_1_3_2_1_17_1","unstructured":"Henry Corrigan-Gibbs Alexandra Henzinger Yael Kalai and Vinod Vaikuntanathan. 2024. Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN. Cryptology ePrint Archive Paper 2024\/1760. https:\/\/eprint.iacr.org\/2024\/1760"},{"key":"e_1_3_2_1_18_1","unstructured":"Henry Corrigan-Gibbs Alexandra Henzinger Yael Kalai and Vinod Vaikuntanathan. 2024. Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN. Cryptology ePrint Archive Paper 2024\/1760. https:\/\/eprint.iacr.org\/2024\/1760"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84252-9_17"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_21_1","volume-title":"Conference on Learning Theory. 1358\u20131394","author":"Daniely Amit","year":"2021","unstructured":"Amit Daniely and Gal Vardi. 2021. From local pseudorandom generators to hardness of learning. In Conference on Learning Theory. 1358\u20131394. https:\/\/proceedings.mlr.press\/v134\/daniely21a\/daniely21a.pdf"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_11"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68382-4_2"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34961-4_30"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.78"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00026"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519955"},{"key":"e_1_3_2_1_30_1","volume-title":"Statistical Inference and the Sum of Squares Method. Ph. D. Dissertation","author":"Hopkins Samuel B","unstructured":"Samuel B Hopkins. 2018. Statistical Inference and the Sum of Squares Method. Ph. D. Dissertation. Cornell University. https:\/\/www.samuelbhopkins.com\/thesis.pdf"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_32_1","volume-title":"Fundamentals of error-correcting codes (1 ed.)","author":"William W. C.","unstructured":"W. C. (William Cary) Huffman. 2003. Fundamentals of error-correcting codes (1 ed.). Cambridge University Press,, Cambridge, U.K. ; New York :. isbn:0-521-13170-7"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374438"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_18"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-68382-4_7"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451093"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-4_23"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055485"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"A. K. Lenstra H. W. Lenstra and L. Lov\u00e1sz. 1982. Factoring polynomials with rational coefficients. Mathematische annalen 261 4 (1982) 515\u2013534. issn:0025-5831","DOI":"10.1007\/BF01457454"},{"key":"e_1_3_2_1_40_1","volume-title":"Wilmer","author":"Levin David A.","year":"2006","unstructured":"David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. 2006. Markov chains and mixing times. American Mathematical Society. http:\/\/scholar.google.com\/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com\/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21748"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","unstructured":"Mihai Patrascu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. 1065\u20131075. https:\/\/doi.org\/10.5555\/1873601.1873687","DOI":"10.5555\/1873601.1873687"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536461"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Seyoon Ragavan Neekon Vafa and Vinod Vaikuntanathan. 2024. Indistinguishability Obfuscation from Bilinear Maps and LPN Variants. Cryptology ePrint Archive Paper 2024\/856. https:\/\/eprint.iacr.org\/2024\/856","DOI":"10.1007\/978-3-031-78023-3_1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055417"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.641542"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:48:15Z","timestamp":1750693695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":48,"alternative-id":["10.1145\/3717823.3718284","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718284","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}