{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T01:58:51Z","timestamp":1775181531207,"version":"3.50.1"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2017,10,9]],"date-time":"2017-10-09T00:00:00Z","timestamp":1507507200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Finding a hidden partition in a random environment is a general and important problem which contains as subproblems many important questions, such as finding a hidden clique, finding a hidden colouring, finding a hidden bipartition,<jats:italic>etc<\/jats:italic>.<\/jats:p><jats:p>In this paper we provide a simple SVD algorithm for this purpose, addressing a question of McSherry. This algorithm is easy to implement and works for sparse graphs under optimal density assumptions. We also consider an approximating algorithm, which on one hand works under very mild assumptions, but on other hand can sometimes be upgraded to give the exact solution.<\/jats:p>","DOI":"10.1017\/s0963548317000463","type":"journal-article","created":{"date-parts":[[2017,10,9]],"date-time":"2017-10-09T09:31:34Z","timestamp":1507541494000},"page":"124-140","source":"Crossref","is-referenced-by-count":29,"title":["A Simple SVD Algorithm for Finding Hidden Partitions"],"prefix":"10.1017","volume":"27","author":[{"given":"VAN","family":"VU","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2017,10,9]]},"reference":[{"key":"S0963548317000463_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548317000463_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A"},{"key":"S0963548317000463_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20561"},{"key":"S0963548317000463_ref21","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366878"},{"key":"S0963548317000463_ref33","volume-title":"Clustering","author":"Xu","year":"2014"},{"key":"S0963548317000463_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579448"},{"key":"S0963548317000463_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"S0963548317000463_ref25","first-page":"A\u2013382","article-title":"The employee party problem","volume":"19","author":"Matula","year":"1972","journal-title":"Notices Amer. Math. Soc."},{"key":"S0963548317000463_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08442-8_114"},{"key":"S0963548317000463_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90005-3"},{"key":"S0963548317000463_ref28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aop\/1042644705","article-title":"A new look at independence","volume":"24","author":"Talagrand","year":"1996","journal-title":"Ann. Probab."},{"key":"S0963548317000463_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/0707001"},{"key":"S0963548317000463_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73063"},{"key":"S0963548317000463_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20089"},{"key":"S0963548317000463_ref23","volume-title":"Spectral Algorithms","author":"Kannan","year":"2009"},{"key":"S0963548317000463_ref9","first-page":"391","article-title":"Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery","volume":"40","author":"Chin","year":"2015","journal-title":"Proc. of Machine Learning Research"},{"key":"S0963548317000463_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794270248"},{"key":"S0963548317000463_ref6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1034"},{"key":"S0963548317000463_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2190-z"},{"key":"S0963548317000463_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990514"},{"key":"S0963548317000463_ref15","doi-asserted-by":"crossref","unstructured":"Dyer M. E. and Frieze A. M. (1986) Fast solution of some random NP-hard problems. In 27th Annual Symposium on Foundations of Computer Science, IEEE, pp. 221\u2013336.","DOI":"10.1109\/SFCS.1986.17"},{"key":"S0963548317000463_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579329"},{"key":"S0963548317000463_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973013.8"},{"key":"S0963548317000463_ref7","doi-asserted-by":"crossref","unstructured":"Boppana R. B. (1987) Eigenvalues and graph bisection: An average-case analysis. In SFCS '87: Proc. 28th Annual Symposium on Foundations of Computer Science, ACM, pp. 280\u2013285.","DOI":"10.1109\/SFCS.1987.22"},{"key":"S0963548317000463_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9215-y"},{"key":"S0963548317000463_ref27","doi-asserted-by":"crossref","unstructured":"McSherry F. (2001) Spectral partitioning of random graphs. In FOCS 2001: Proc. 42nd IEEE Symposium on Foundations of Computer Science, IEEE, pp. 529\u2013537.","DOI":"10.1109\/SFCS.2001.959929"},{"key":"S0963548317000463_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"S0963548317000463_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01932678"},{"key":"S0963548317000463_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380859"},{"key":"S0963548317000463_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2"},{"key":"S0963548317000463_ref18","doi-asserted-by":"crossref","unstructured":"Feige U. and Ron D. (2010) Finding hidden cliques in linear time. In AofA'10: 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, DMTCS Proc. AM, pp. 189\u2013204.","DOI":"10.46298\/dmtcs.2802"},{"key":"S0963548317000463_ref20","volume-title":"Matrix Computations","author":"Golub","year":"1996"},{"key":"S0963548317000463_ref4","volume-title":"Spectral Analysis of Large Dimensional Random Matrices","author":"Bai","year":"2009"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T03:25:08Z","timestamp":1659583508000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000463\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,9]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["S0963548317000463"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000463","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,9]]}}}