{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T21:43:14Z","timestamp":1774042994083,"version":"3.50.1"},"reference-count":64,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"4","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2023YFA1010103"],"award-info":[{"award-number":["2023YFA1010103"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC Key Program","doi-asserted-by":"publisher","award":["12231002"],"award-info":[{"award-number":["12231002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1109\/tit.2026.3659093","type":"journal-article","created":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T21:23:04Z","timestamp":1769721784000},"page":"2444-2456","source":"Crossref","is-referenced-by-count":0,"title":["A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials"],"prefix":"10.1109","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-7182-8639","authenticated-orcid":false,"given":"Zhangsong","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref1","article-title":"Linear regression with shuffled labels","author":"Abid","year":"2017","journal-title":"arXiv:1705.01342"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511801334"},{"key":"ref3","first-page":"105","article-title":"Correspondence retrieval","volume-title":"Proc. 30th Conf. Learn. Theory (COLT)","author":"Andoni"},{"key":"ref4","first-page":"1","article-title":"Computational hardness of certifying bounds on constrained PCA problems","volume-title":"Proc. 11th Innov. Theor. Comput. Sci. Conf.","volume":"151","author":"Bandeira"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.52202\/068431-2452"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"ref7","first-page":"774","article-title":"Statistical query algorithms and low-degree tests are almost equivalent","volume-title":"Proc. 34th Conf. Learn. Theory (COLT)","author":"Brennan"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00038"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451000"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20633"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00134"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1214\/25-aos2565"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT44484.2020.9174507"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21279"},{"key":"ref15","first-page":"4535","article-title":"Non-Gaussian component analysis via lattice basis reduction","volume-title":"Proc. 35th Annu. Conf. Learn. Theory (COLT)","author":"Diakonikolas"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00063"},{"key":"ref17","first-page":"2319","article-title":"SQ lower bounds for learning mixtures of separated and bounded covariance Gaussians","volume-title":"Proc. 36th Annu. Conf. Learn. Theory (COLT)","author":"Diakonikolas"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1214\/25-AOS2517"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-023-09603-0"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/16M1078628"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.52202\/079017-2260"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2108492118"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00021"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1002\/sapm195938177"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00093"},{"key":"ref26","article-title":"The umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime","author":"Gong","year":"2024","journal-title":"arXiv:2402.15095"},{"key":"ref27","article-title":"The broken-sample problem revisited II: Detecting hidden linear dependencies","author":"Gong","year":"2025"},{"key":"ref28","first-page":"1880","article-title":"Unsupervised alignment of embeddings with Wasserstein procrustes","volume-title":"Proc. 22nd Int. Conf. Artif. Intell. Statist. (AISTATS)","author":"Grave"},{"key":"ref29","first-page":"1","article-title":"Counterexamples to the low-degree conjecture","volume-title":"Proc. 12th Innov. Theor. Comput. Sci. Conf. (ITCS)","author":"Holmgren"},{"key":"ref30","article-title":"Statistical inference and the sum of squares method","author":"Hopkins","year":"2018"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"key":"ref33","first-page":"1531","article-title":"Linear regression without correspondence","volume-title":"Proc. Adv. Neural Inf. Process. Syst. (NIPS)","volume":"30","author":"Hsu"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7470"},{"key":"ref35","article-title":"The broken sample problem revisited: Proof of a conjecture by bai-hsing and high-dimensional extensions","author":"Jiao","year":"2025","journal-title":"arXiv:2503.14619"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585221"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1214\/24-aos2484"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00067"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.36"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-97127-4_1"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT57864.2024.10619515"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-11761-3"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925913"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01863-y"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-012-0423-6"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/springerreference_330"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-024-01322-z"},{"key":"ref48","article-title":"Approximate random geometric graph matching","author":"Niu","year":"2025"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2776217"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0186"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63046-5_3"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1214\/22-AOS2179"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1214\/18-EJS1498"},{"issue":"204","key":"ref54","first-page":"1","article-title":"Two-stage approach to multivariate linear regression with sparsely mismatched data","volume":"21","author":"Slawski","year":"2020","journal-title":"J. Mach. Learn. Res."},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/023"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2809002"},{"key":"ref57","first-page":"3441","article-title":"Random graph matching in geometric models: The case of complete graphs","volume-title":"Proc. 35th Conf. Learn. Theory (COLT)","author":"Wang"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.4171\/msl\/25"},{"key":"ref59","article-title":"Computational complexity of statistics: New insights from low-degree polynomials","author":"Wein","year":"2025","journal-title":"arXiv:2506.10748"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.2307\/2331939"},{"key":"ref61","first-page":"1247","article-title":"Lattice-based methods surpass sum-of-squares in clustering","volume-title":"Proc. 35th Conf. Learn. Theory (COLT)","author":"Zadik"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"},{"key":"ref63","first-page":"11153","article-title":"Optimal estimator for unlabeled linear regression","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Zhang"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3127072"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/18\/11448285\/11367781.pdf?arnumber=11367781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T19:57:50Z","timestamp":1774036670000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/11367781\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4]]},"references-count":64,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.1109\/tit.2026.3659093","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4]]}}}