{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:02Z","timestamp":1781031422943,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":57,"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":[{"name":"Swiss National Science Foundation","award":["P500-2 235374"],"award-info":[{"award-number":["P500-2 235374"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800883","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1763-1770","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Rigorous Implications of the Low-Degree Heuristic"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8762-9658","authenticated-orcid":false,"given":"Jun-Ting","family":"Hsieh","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9647-2609","authenticated-orcid":false,"given":"Daniel M.","family":"Kane","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8689-6770","authenticated-orcid":false,"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5035-3728","authenticated-orcid":false,"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8794-7616","authenticated-orcid":false,"given":"Sidhanth","family":"Mohanty","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9719-0036","authenticated-orcid":false,"given":"Stefan","family":"Tiegel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Workshop on Low Degree Polynomial Methods in Average Case Complexity. http:\/\/admin.aimath.org\/resources\/lowdegreecomplexity\/participantlist\/","unstructured":"2024. Workshop on Low Degree Polynomial Methods in Average Case Complexity. http:\/\/admin.aimath.org\/resources\/lowdegreecomplexity\/participantlist\/"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-48615-9_11"},{"key":"e_1_3_2_1_3_1","unstructured":"Kwangjun Ahn Dhruv Medarametla and Aaron Potechin. 2016. Graph matrices: Norm bounds and applications. arXiv preprint arXiv:1604.03423."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.19"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2810020"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.53"},{"key":"e_1_3_2_1_7_1","unstructured":"Ross Berkowitz. 2018. A local limit theorem for cliques in G(n p). arXiv preprint arXiv:1811.03527."},{"key":"e_1_3_2_1_8_1","volume-title":"Conference on learning theory. 1046\u20131066","author":"Berthet Quentin","year":"2013","unstructured":"Quentin Berthet and Philippe Rigollet. 2013. Complexity theoretic lower bounds for sparse principal component detection. In Conference on learning theory. 1046\u20131066."},{"key":"e_1_3_2_1_9_1","volume-title":"13th Innovations in Theoretical Computer Science Conference (ITCS","author":"Bogdanov Andrej","year":"2022","unstructured":"Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. 2022. Bounded indistinguishability for simple sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). 26\u20131."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_21"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78017-2_9"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-48615-9_10"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019970"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754401"},{"key":"e_1_3_2_1_15_1","volume-title":"Conference on Learning Theory. 648\u2013847","author":"Brennan Matthew","year":"2020","unstructured":"Matthew Brennan and Guy Bresler. 2020. Reducibility and statistical-computational gaps from secret leakage. In Conference on Learning Theory. 648\u2013847."},{"key":"e_1_3_2_1_16_1","volume-title":"Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent. In Conference on Learning Theory. 774\u2013774","author":"Brennan Matthew S","year":"2021","unstructured":"Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, and Tselil Schramm. 2021. Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent. In Conference on Learning Theory. 774\u2013774."},{"key":"e_1_3_2_1_17_1","unstructured":"Guy Bresler and Alina Harbuzova. 2025. Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation. arXiv preprint arXiv:2503.02802."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00134"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-007-0118-6"},{"key":"e_1_3_2_1_20_1","unstructured":"Zongchen Chen Dan Mikulincer Daniel Reichman and Alexander S Wein. 2023. Time Lower Bounds for the Metropolis Process and Simulated Annealing. arXiv preprint arXiv:2312.13554."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21274"},{"key":"e_1_3_2_1_22_1","unstructured":"Zongchen Chen Conor Sheehan and Ilias Zadik. 2024. On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA sparse regression and a geometric rule. arXiv preprint arXiv:2408.00746."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783030"},{"key":"e_1_3_2_1_24_1","volume-title":"Conference on Learning Theory. 4535\u20134547","author":"Diakonikolas Ilias","year":"2022","unstructured":"Ilias Diakonikolas and Daniel Kane. 2022. Non-Gaussian Component Analysis via Lattice Basis Reduction. In Conference on Learning Theory. 4535\u20134547."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.8"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-023-09603-0"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00093"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1448"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M150263X"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00093"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20604"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Oded Goldreich. 2011. Notes on Levin\u2019s theory of average-case complexity. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad Mihir Bellare Zvika Brakerski Shafi Goldwasser Shai Halevi Tali Kaufman Leonid Levin Noam Nisan Dana Ron Madhu Sudan Luca Trevisan Salil Vadhan Avi Wigderson David Zuckerman 233\u2013247.","DOI":"10.1007\/978-3-642-22670-0_21"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1129088"},{"key":"e_1_3_2_1_36_1","volume-title":"12th Innovations in Theoretical Computer Science Conference (ITCS","author":"Holmgren Justin","year":"2021","unstructured":"Justin Holmgren and Alexander S Wein. 2021. Counterexamples to the Low-Degree Conjecture. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)."},{"key":"e_1_3_2_1_37_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_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2009.0121"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00048"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585221"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.13"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649703"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01558-2"},{"key":"e_1_3_2_1_48_1","volume-title":"ISAAC Congress (International Society for Analysis, its Applications and Computation). 1\u201350","author":"Kunisky Dmitriy","year":"2019","unstructured":"Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. 2019. Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation). 1\u201350."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a007"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384319"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2637959"},{"key":"e_1_3_2_1_53_1","volume-title":"Sums of independent random variables. 82","author":"Petrov Valentin V","unstructured":"Valentin V Petrov. 2012. Sums of independent random variables. 82, Springer Science & Business Media."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12523"},{"key":"e_1_3_2_1_55_1","volume-title":"On mean convergence for densities. Teor. Verojatnost. i Primenen, 7","author":"Sirazdinov SH","year":"1962","unstructured":"SH Sirazdinov and M Mamatov. 1962. On mean convergence for densities. Teor. Verojatnost. i Primenen, 7 (1962), 433\u2013437."},{"key":"e_1_3_2_1_56_1","unstructured":"Alexander S Wein. 2025. Computational Complexity of Statistics: New Insights from Low-Degree Polynomials. arXiv preprint arXiv:2506.10748."},{"key":"e_1_3_2_1_57_1","volume-title":"Lattice-Based Methods Surpass Sum-of-Squares in Clustering. In Conference on Learning Theory. 1247\u20131248","author":"Zadik Ilias","year":"2022","unstructured":"Ilias Zadik, Min Jae Song, Alexander S Wein, and Joan Bruna. 2022. Lattice-Based Methods Surpass Sum-of-Squares in Clustering. In Conference on Learning Theory. 1247\u20131248."}],"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.3800883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:00:02Z","timestamp":1781028002000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":57,"alternative-id":["10.1145\/3798129.3800883","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800883","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"}}]}}