{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T09:55:12Z","timestamp":1740131712987,"version":"3.37.3"},"reference-count":58,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"6","license":[{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1734\/21","1766\/22"],"award-info":[{"award-number":["1734\/21","1766\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1734\/21"],"award-info":[{"award-number":["1734\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1766\/22"],"award-info":[{"award-number":["1766\/22"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2024,6]]},"DOI":"10.1109\/tit.2024.3382228","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T20:11:13Z","timestamp":1711483873000},"page":"4319-4334","source":"Crossref","is-referenced-by-count":0,"title":["Planted Bipartite Graph Detection"],"prefix":"10.1109","volume":"70","author":[{"given":"Asaf","family":"Rotenberg","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering-Systems, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7500-1911","authenticated-orcid":false,"given":"Wasim","family":"Huleihel","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering-Systems, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4321-0318","authenticated-orcid":false,"given":"Ofer","family":"Shayevitz","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering-Systems, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1860"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.53"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831300045X"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"},{"key":"ref8","first-page":"899","article-title":"Computational lower bounds for community detection on random graphs","volume-title":"Proc. 28th Conf. Learn. Theory","volume":"40","author":"Hajek"},{"issue":"27","key":"ref9","first-page":"1","article-title":"Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices","volume":"17","author":"Chen","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref10","first-page":"48","article-title":"Reducibility and computational lower bounds for problems with planted sparse structure","volume-title":"Proc. 31st Conf. Learn. Theory","volume":"75","author":"Brennan"},{"key":"ref11","first-page":"2341","article-title":"Planting trees in graphs, and finding them back","volume-title":"Proc. 32nd Conf. Learn. Theory","volume":"99","author":"Massoulie"},{"key":"ref12","first-page":"1761","article-title":"On the evolution of random graphs","volume":"5","author":"Erdos","year":"1960","journal-title":"Publication Math. Inst. Hung. Acad. Sci."},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100058655"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.42"},{"article-title":"Statistical inference and the sum of squares method","year":"2018","author":"Hopkins","key":"ref15"},{"key":"ref16","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":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384329"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00021"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TSIPN.2022.3211208"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1208"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1080"},{"key":"ref22","first-page":"1046","article-title":"Complexity theoretic lower bounds for sparse principal component detection","volume-title":"Proc. 26th Annu. Conf. Learn. Theory","volume":"30","author":"Berthet"},{"issue":"1","key":"ref23","first-page":"6446","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1017\/9781108616799.014"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1886"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511984068"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1093\/gigascience\/giy014"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1300"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1488"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1310"},{"key":"ref31","first-page":"3819","article-title":"Average-case hardness of RIP certification","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Wang"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1369"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1519"},{"key":"ref34","first-page":"417","article-title":"Universality of computational lower bounds for submatrix detection","volume-title":"Proc. 32nd Conf. Learn. Theory","volume":"99","author":"Brennan"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1017\/9781108616799.014"},{"key":"ref36","first-page":"648","article-title":"Reducibility and statistical-computational gaps from secret leakage","volume-title":"Proc. 33rd Conf. Learn. Theory","volume":"125","author":"Brennan"},{"key":"ref37","first-page":"523","article-title":"Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems","volume-title":"Proc. 28th Conf. Learn. Theory","volume":"40","author":"Deshpande"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746600"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00048"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055485"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1145\/3178538"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0186"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384319"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746577"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.170"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7447070"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2016.7852287"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.99.042109"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.4171\/PM\/2014"},{"key":"ref54","first-page":"909","article-title":"Minimax localization of structural information in large noisy matrices","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Kolar"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.3150\/12-BEJ470"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-97127-4_1"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1214\/22-AOS2179"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/10536118\/10479583.pdf?arnumber=10479583","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T04:51:59Z","timestamp":1716439919000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10479583\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":58,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.1109\/tit.2024.3382228","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"type":"print","value":"0018-9448"},{"type":"electronic","value":"1557-9654"}],"subject":[],"published":{"date-parts":[[2024,6]]}}}