{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:58:25Z","timestamp":1781218705879,"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","volume-title":"Graph matrices: Norm bounds and applications. arXiv preprint arXiv:1604.03423","author":"Ahn Kwangjun","year":"2016","unstructured":"Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. 2016. Graph matrices: Norm bounds and applications. arXiv preprint arXiv:1604.03423 (2016)."},{"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","volume-title":"A local limit theorem for cliques in \ud835\udc3a (\ud835\udc5b, \ud835\udc5d ). arXiv preprint arXiv:1811.03527","author":"Berkowitz Ross","year":"2018","unstructured":"Ross Berkowitz. 2018. A local limit theorem for cliques in \ud835\udc3a (\ud835\udc5b, \ud835\udc5d ). arXiv preprint arXiv:1811.03527 (2018)."},{"key":"e_1_3_2_1_8_1","volume-title":"Conference on learning theory. PMLR, 1046-1066","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. PMLR, 1046-1066."},{"key":"e_1_3_2_1_9_1","first-page":"26","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). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 26-1."},{"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-"},{"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","volume-title":"Average-case complexity. Foundations and Trends\u00ae in Theoretical Computer Science 2, 1","author":"Bogdanov Andrej","year":"2006","unstructured":"Andrej Bogdanov and Luca Trevisan. 2006. Average-case complexity. Foundations and Trends\u00ae in Theoretical Computer Science 2, 1 (2006), 1-106."},{"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. PMLR, 648-847","author":"Brennan Matthew","year":"2020","unstructured":"Matthew Brennan and Guy Bresler. 2020. Reducibility and statisticalcomputational gaps from secret leakage. In Conference on Learning Theory. PMLR, 648-847."},{"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. PMLR, 774-774","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. PMLR, 774-774."},{"key":"e_1_3_2_1_17_1","volume-title":"Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation. arXiv preprint arXiv:2503.02802","author":"Bresler Guy","year":"2025","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 (2025)."},{"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","volume-title":"Time Lower Bounds for the Metropolis Process and Simulated Annealing. arXiv preprint arXiv:2312.13554","author":"Chen Zongchen","year":"2023","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 (2023)."},{"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","volume-title":"On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule. arXiv preprint arXiv:2408.00746","author":"Chen Zongchen","year":"2024","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 (2024)."},{"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. PMLR, 4535-4547","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. PMLR, 4535-4547."},{"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","volume-title":"Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan","author":"Goldreich Oded","year":"2011","unstructured":"Oded Goldreich. 2011. Notes on Levin's 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 (2011), 233-247."},{"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). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik."},{"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"},{"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). Springer, 1-50","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). Springer, 1-50."},{"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","author":"Petrov Valentin V","unstructured":"Valentin V Petrov. 2012. Sums of independent random variables. Vol. 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-437."},{"key":"e_1_3_2_1_56_1","volume-title":"Computational Complexity of Statistics: New Insights from Low-Degree Polynomials. arXiv preprint arXiv:2506.10748","author":"Wein Alexander S","year":"2025","unstructured":"Alexander S Wein. 2025. Computational Complexity of Statistics: New Insights from Low-Degree Polynomials. arXiv preprint arXiv:2506.10748 (2025)."},{"key":"e_1_3_2_1_57_1","volume-title":"Lattice-Based Methods Surpass Sum-of-Squares in Clustering. In Conference on Learning Theory. PMLR, 1247-1248","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. PMLR, 1247-1248."}],"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,11]],"date-time":"2026-06-11T22:32:55Z","timestamp":1781217175000},"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"}}]}}