{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:27Z","timestamp":1781028267808,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":69,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800905","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2007-2018","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational and Statistical Lower Bounds for Low-Rank Estimation under General Inhomogeneous Noise"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5360-3871","authenticated-orcid":false,"given":"Debsurya","family":"De","sequence":"first","affiliation":[{"name":"Johns Hopkins University, Applied Mathematics & Statistics, Baltimore, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0854-4067","authenticated-orcid":false,"given":"Dmitriy","family":"Kunisky","sequence":"additional","affiliation":[{"name":"Johns Hopkins University, Applied Mathematics & Statistics, Baltimore, 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.1109\/TNSE.2014.2368716"},{"key":"e_1_3_2_1_2_1","unstructured":"Kwangjun Ahn Dhruv Medarametla and Aaron Potechin. 2016. Graph matrices: Norm bounds and applications. arXiv preprint arXiv:1604.03423 arxiv:1604.03423."},{"key":"e_1_3_2_1_3_1","volume-title":"Quadratic vector equations on complex upper half-plane. 261","author":"Ajanki Oskari","unstructured":"Oskari Ajanki, L\u00e1szl\u00f3 Erd\u0151s, and Torben Kr\u00fcger. 2019. Quadratic vector equations on complex upper half-plane. 261, American Mathematical Society."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0740-2"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-020-02684-z"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04165-0"},{"key":"e_1_3_2_1_7_1","article-title":"A statistical physics approach to a multi-channel Wigner spiked model","volume":"136","author":"Alberici Diego","year":"2022","unstructured":"Diego Alberici, Francesco Camilli, Pierluigi Contucci, and Emanuele Mingione. 2022. A statistical physics approach to a multi-channel Wigner spiked model. Europhysics Letters, 136, 4 (2022).","journal-title":"Europhysics Letters"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1447"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-0661-8"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of Thirty Fourth Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"473","author":"Bandeira Afonso S","year":"2021","unstructured":"Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S Wein. 2021. Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Proceedings of Thirty Fourth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 134). PMLR, 410\u2013473."},{"key":"e_1_3_2_1_11_1","unstructured":"Afonso S Bandeira March T Boedihardjo and Ramon van Handel. 2021. Matrix Concentration Inequalities and Free Probability. arXiv preprint arXiv:2108.06312 arxiv:2108.06312."},{"key":"e_1_3_2_1_12_1","unstructured":"Afonso S Bandeira Giorgio Cipolloni Dominik Schr\u00f6der and Ramon van Handel. 2024. Matrix Concentration Inequalities and Free Probability II. Two-sided Bounds and Applications. arXiv preprint arXiv:2406.11453 arxiv:2406.11453."},{"key":"e_1_3_2_1_13_1","volume-title":"Samuel B Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik.","author":"Bandeira Afonso S","year":"2022","unstructured":"Afonso S Bandeira, Ahmed El Alaoui, Samuel B Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. 2022. The Franz-Parisi criterion and computational trade-offs in high dimensional statistics. arXiv preprint arXiv:2205.09727, arxiv:2205.09727."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1025"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2810020"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2302028120"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.7.013081"},{"key":"e_1_3_2_1_19_1","unstructured":"Jean Barbier Mohamad Dia Nicolas Macris Florent Krzakala Thibault Lesieur and Lenka Zdeborov\u00e1. 2016. Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. arXiv preprint arXiv:1606.04142 arxiv:1606.04142."},{"key":"e_1_3_2_1_20_1","unstructured":"Jean Barbier Mohamad Dia Nicolas Macris Florent Krzakala and Lenka Zdeborov\u00e1. 2018. Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method. arXiv preprint arXiv:1812.02537 arxiv:1812.02537."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-2662"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT44484.2020.9173970"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research","volume":"8672","author":"Joshua","unstructured":"Joshua K. Behne and Galen Reeves. 2022. Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 151). PMLR, 8650\u20138672."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.02.007"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaaa012"},{"key":"e_1_3_2_1_26_1","unstructured":"Mireille Capitaine. 2017. Deformed ensembles polynomials in random matrices and free probability theory. Ph. D. Dissertation. Universit\u00e9 Paul Sabatier-Toulouse 3."},{"key":"e_1_3_2_1_27_1","unstructured":"Mireille Capitaine and Catherine Donati-Martin. 2016. Spectrum of deformed random matrices and free probability. arXiv preprint arXiv:1607.05560 arxiv:1607.05560."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOP394"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v16-934"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of Thirty Fifth Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"4781","author":"Coja-Oghlan Amin","year":"2022","unstructured":"Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, and Ilias Zadik. 2022. Statistical and Computational Phase Transitions in Group Testing. In Proceedings of Thirty Fifth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 178). PMLR, 4764\u20134781."},{"key":"e_1_3_2_1_31_1","unstructured":"Debsurya De and Dmitriy Kunisky. 2025. Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise. arXiv preprint arXiv:2510.08541 arxiv:2510.08541."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Yash Deshpande Emmanuel Abbe and Andrea Montanari. 2015. Asymptotic mutual information for the two-groups stochastic block model. arXiv preprint arXiv:1507.08685 arxiv:1507.08685.","DOI":"10.1093\/imaiai\/iaw017"},{"key":"e_1_3_2_1_33_1","unstructured":"Abhishek Dhawan Cheng Mao and Alexander S Wein. 2023. Detection of Dense Subhypergraphs by Low-Degree Polynomials. arXiv preprint arXiv:2304.08135 arxiv:2304.08135."},{"key":"e_1_3_2_1_34_1","unstructured":"Jian Ding Hang Du and Zhangsong Li. 2023. Low-degree hardness of detection for correlated Erd\u0151s-R\u00e9nyi graphs. arXiv preprint arXiv:2311.15931 arxiv:2311.15931."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1826"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-007-0209-3"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaaf010"},{"key":"e_1_3_2_1_39_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."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.49"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.78"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1009210544"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2846730"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2016.7606798"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1214\/24-AOS2484"},{"key":"e_1_3_2_1_48_1","unstructured":"Dmitriy Kunisky Cristopher Moore and Alexander S Wein. 2024. Tensor cumulants for statistical inference on invariant distributions. arXiv preprint arXiv:2404.18735 arxiv:2404.18735."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-97127-4_1"},{"key":"e_1_3_2_1_50_1","volume-title":"The dimension-free structure of nonhomogeneous random matrices. Inventiones mathematicae, 214","author":"Rafa\u0142 Lata\u0142","year":"2018","unstructured":"Rafa\u0142 Lata\u0142 a, Ramon van Handel, and Pierre Youssef. 2018. The dimension-free structure of nonhomogeneous random matrices. Inventiones mathematicae, 214 (2018), 1031\u20131080."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1017\/jpr.2023.44"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-018-0845-x"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7447070"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2015.7282733"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/aa7284"},{"key":"e_1_3_2_1_56_1","unstructured":"Pierre Mergny Justin Ko and Florent Krzakala. 2024. Spectral phase transition and optimal PCA in block-structured spiked models. arXiv preprint arXiv:2403.03695 arxiv:2403.03695."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2011.12.010"},{"key":"e_1_3_2_1_58_1","unstructured":"Ankur Moitra and Alexander S Wein. 2023. Precise Error Rates for Computationally Efficient Testing. arXiv preprint arXiv:2311.00289 arxiv:2311.00289."},{"key":"e_1_3_2_1_59_1","first-page":"76409","article-title":"Optimal algorithms for the inhomogeneous spiked Wigner model","volume":"36","author":"Pak Aleksandr","year":"2023","unstructured":"Aleksandr Pak, Justin Ko, and Florent Krzakala. 2023. Optimal algorithms for the inhomogeneous spiked Wigner model. Advances in Neural Information Processing Systems, 36 (2023), 76409\u201376424.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1625"},{"key":"e_1_3_2_1_61_1","unstructured":"Aaron Potechin Prayaag Venkat Paxton Turner and Alexander S Wein. 2022. Near-optimal fitting of ellipsoids to random points. arXiv preprint arXiv:2208.09493 arxiv:2208.09493."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2020.3040598"},{"key":"e_1_3_2_1_63_1","unstructured":"Riccardo Rossetti and Galen Reeves. 2025. Statistical Limits for Finite-Rank Tensor Estimation. arXiv preprint arXiv:2506.06749 arxiv:2506.06749."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2015.7282642"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1155\/S1073792896000633"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"crossref","unstructured":"Ramon van Handel. 2017. Structured random matrices. Convexity and concentration 107\u2013156.","DOI":"10.1007\/978-1-4939-7005-6_4"},{"key":"e_1_3_2_1_67_1","unstructured":"Alexander S Wein. 2025. Computational Complexity of Statistics: New Insights from Low-Degree Polynomials. arXiv preprint arXiv:2506.10748 arxiv:2506.10748."},{"key":"e_1_3_2_1_68_1","first-page":"93060","article-title":"Matrix denoising with doubly heteroscedastic noise: Fundamental limits and optimal spectral methods","volume":"37","author":"Zhang Yihan","year":"2024","unstructured":"Yihan Zhang and Marco Mondelli. 2024. Matrix denoising with doubly heteroscedastic noise: Fundamental limits and optimal spectral methods. Advances in Neural Information Processing Systems, 37 (2024), 93060\u201393117.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20894"}],"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.3800905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:54:47Z","timestamp":1781027687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":69,"alternative-id":["10.1145\/3798129.3800905","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800905","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"}}]}}