{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:36Z","timestamp":1781028336915,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2217033"],"award-info":[{"award-number":["CCF-2217033"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2505865"],"award-info":[{"award-number":["CCF-2505865"]}],"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":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800926","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2242-2253","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparse Linear Regression Is Easy on Random Supports"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2443-8675","authenticated-orcid":false,"given":"Gautam","family":"Chandrasekaran","sequence":"first","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7676-2762","authenticated-orcid":false,"given":"Raghu","family":"Meka","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2643-4298","authenticated-orcid":false,"given":"Konstantinos","family":"Stavropoulos","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOS620"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"771","author":"Buhai Rares-Darius","year":"2024","unstructured":"Rares-Darius Buhai, Jingqiu Ding, and Stefan Tiegel. 2024. Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 752\u2013771. https:\/\/proceedings.mlr.press\/v247\/buhai24a.html"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053606000001523"},{"key":"e_1_3_2_1_6_1","unstructured":"Gautam Chandrasekaran Raghu Meka and Konstantinos Stavropoulos. 2025. Sparse Linear Regression is Easy on Random Supports. arXiv preprint arxiv:2511.06211."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.3150\/15-BEJ756"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0149053"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-economics-061109-080451"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research","volume":"709","author":"Foster Dean","year":"2015","unstructured":"Dean Foster, Howard Karloff, and Justin Thaler. 2015. Variable Selection is Hard. In Proceedings of The 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research, Vol. 40). PMLR, Paris, France. 696\u2013709. https:\/\/proceedings.mlr.press\/v40\/Foster15.html"},{"key":"e_1_3_2_1_12_1","unstructured":"Rina Foygel and Nathan Srebro. 2011. Fast-rate and optimistic-rate error bounds for L1-regularized regression. arXiv preprint arxiv:1108.0373."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78017-2_10"},{"key":"e_1_3_2_1_14_1","unstructured":"Aparna Gupte and Vinod Vaikuntanathan. 2021. The fine-grained hardness of sparse linear regression. arXiv preprint arxiv:2106.03131."},{"key":"e_1_3_2_1_15_1","volume-title":"Statistical Inference and the Sum of Squares Method. Ph. D. Dissertation","author":"Hopkins Samuel","unstructured":"Samuel Hopkins. 2018. Statistical Inference and the Sum of Squares Method. Ph. D. Dissertation. Cornell University."},{"key":"e_1_3_2_1_16_1","volume-title":"Advances in Neural Information Processing Systems","author":"Kelner Jonathan","year":"2020","unstructured":"Jonathan Kelner, Frederic Koehler, Raghu Meka, and Ankur Moitra. 2020. Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.). 33, Curran Associates, Inc., 10986\u201310998. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2020\/file\/7cc980b0f894bd0cf05c37c246f215f3-Paper.pdf"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-1773"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-1305"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"2886","author":"Kelner Jonathan","year":"2024","unstructured":"Jonathan Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. 2024. Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 2840\u20132886. https:\/\/proceedings.mlr.press\/v247\/kelner24a.html"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00061"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1190\/1.1441261"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240406"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2165799"},{"key":"e_1_3_2_1_24_1","unstructured":"Philippe Rigollet and Jan-Christian H\u00fctter. 2023. High-dimensional statistics. arXiv preprint arxiv:2310.19244."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"I. Rish G.A. Cecchi A. Lozano and A. Niculescu-Mizil. 2014. Practical Applications of Sparse Modeling. MIT Press. isbn:9780262325332 https:\/\/books.google.com\/books?id=vGsiBQAAQBAJ","DOI":"10.7551\/mitpress\/9333.001.0001"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0907087"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-EJS506"},{"key":"e_1_3_2_1_29_1","volume-title":"High-Dimensional Statistics: A Non-Asymptotic Viewpoint","author":"Wainwright M.J.","year":"2018","unstructured":"M.J. Wainwright. 2019. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press. isbn:9781108498029 lccn:2018043475 https:\/\/books.google.com\/books?id=IluHDwAAQBAJ"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp041"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of The 27th Conference on Learning Theory, Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.) (Proceedings of Machine Learning Research","volume":"948","author":"Zhang Yuchen","unstructured":"Yuchen Zhang, Martin J. Wainwright, and Michael I. Jordan. 2014. Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression. In Proceedings of The 27th Conference on Learning Theory, Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.) (Proceedings of Machine Learning Research, Vol. 35). PMLR, Barcelona, Spain. 921\u2013948. https:\/\/proceedings.mlr.press\/v35\/zhang14.html"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-EJS1233"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800926","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:56:23Z","timestamp":1781027783000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":32,"alternative-id":["10.1145\/3798129.3800926","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800926","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}