{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:57:58Z","timestamp":1781218678484,"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 (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 (Proceedings of Machine Learning Research, Vol. 247), Shipra Agrawal and Aaron Roth (Eds.). PMLR, 752-771. 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","volume-title":"Sparse Linear Regression is Easy on Random Supports. arXiv preprint","author":"Chandrasekaran Gautam","year":"2025","unstructured":"Gautam Chandrasekaran, Raghu Meka, and Konstantinos Stavropoulos. 2025. Sparse Linear Regression is Easy on Random Supports. arXiv preprint (2025). arXiv:2511.06211"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.3150\/15-"},{"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 (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 (Proceedings of Machine Learning Research, Vol. 40), Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.). PMLR, Paris, France, 696-709. https:\/\/proceedings.mlr.press\/v40\/Foster15.html"},{"key":"e_1_3_2_1_12_1","volume-title":"Fast-rate and optimistic-rate error bounds for L1-regularized regression. arXiv preprint","author":"Foygel Rina","year":"2011","unstructured":"Rina Foygel and Nathan Srebro. 2011. Fast-rate and optimistic-rate error bounds for L1-regularized regression. arXiv preprint (2011). 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","volume-title":"The fine-grained hardness of sparse linear regression. arXiv preprint","author":"Gupte Aparna","year":"2021","unstructured":"Aparna Gupte and Vinod Vaikuntanathan. 2021. The fine-grained hardness of sparse linear regression. arXiv preprint (2021). 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","first-page":"10986","volume-title":"Lin (Eds.)","volume":"33","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.), Vol. 33. Curran Associates, Inc., 10986-10998. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2020\/file\/ 7cc980b0f894bd0cf05c37c246f215f3-Paper.pdf"},{"key":"e_1_3_2_1_17_1","first-page":"24419","volume-title":"Oh (Eds.)","volume":"35","author":"Kelner Jonathan","year":"2022","unstructured":"Jonathan Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. 2022. Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran Associates, Inc., 24419-24431. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/ 9a8d52eb05eb7b13f54b3d9eada667b7-Paper-Conference.pdf"},{"key":"e_1_3_2_1_18_1","first-page":"29951","volume-title":"Levine (Eds.)","volume":"36","author":"Kelner Jonathan","year":"2023","unstructured":"Jonathan Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. 2023. Feature Adaptation for Sparse Linear Regression. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Curran Associates, Inc., 29951-29995. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/ 5f999632c48f87cffb214e575581e4a9-Paper-Conference.pdf"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory (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 (Proceedings of Machine Learning Research, Vol. 247), Shipra Agrawal and Aaron Roth (Eds.). PMLR, 2840-2886. 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"},{"key":"e_1_3_2_1_24_1","volume-title":"High-dimensional statistics. arXiv preprint","author":"Rigollet Philippe","year":"2023","unstructured":"Philippe Rigollet and Jan-Christian H\u00fctter. 2023. High-dimensional statistics. arXiv preprint (2023). 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. 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","doi-asserted-by":"publisher","DOI":"10.1017\/9781108627771"},{"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":"Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression. In Proceedings of The 27th Conference on Learning Theory (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 (Proceedings of Machine Learning Research, Vol. 35), Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.). PMLR, Barcelona, Spain, 921-948. https:\/\/proceedings.mlr. press\/v35\/zhang14.html"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-"}],"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,11]],"date-time":"2026-06-11T22:29:19Z","timestamp":1781216959000},"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"}}]}}