{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:46:44Z","timestamp":1770972404675,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T00:00:00Z","timestamp":1410220800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s10208-014-9215-y","type":"journal-article","created":{"date-parts":[[2014,9,8]],"date-time":"2014-09-08T17:29:55Z","timestamp":1410197395000},"page":"1069-1128","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":55,"title":["Finding Hidden Cliques of Size $$\\sqrt{N\/e}$$ N \/ e in Nearly Linear Time"],"prefix":"10.1007","volume":"15","author":[{"given":"Yash","family":"Deshpande","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Montanari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,9,9]]},"reference":[{"key":"9215_CR1","doi-asserted-by":"crossref","unstructured":"Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, and G\u00e1bor Lugosi. On combinatorial testing problems. The Annals of Statistics, 38(5):3063\u20133092, 2010.","DOI":"10.1214\/10-AOS817"},{"key":"9215_CR2","unstructured":"Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pages 594\u2013598. Society for Industrial and Applied Mathematics, 1998."},{"key":"9215_CR3","doi-asserted-by":"crossref","unstructured":"Noga Alon, Michael Krivelevich, and Van\u00a0H Vu. On the concentration of eigenvalues of random symmetric matrices. Israel Journal of Mathematics, 131(1):259\u2013267, 2002.","DOI":"10.1007\/BF02785860"},{"key":"9215_CR4","doi-asserted-by":"crossref","unstructured":"Brendan PW Ames and Stephen A Vavasis. Nuclear norm minimization for the planted clique and biclique problems. Mathematical programming, 129(1):69\u201389, 2011.","DOI":"10.1007\/s10107-011-0459-x"},{"key":"9215_CR5","doi-asserted-by":"crossref","unstructured":"Dana Angluin. Local and global properties in networks of processors. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 82\u201393. ACM, 1980.","DOI":"10.1145\/800141.804655"},{"key":"9215_CR6","doi-asserted-by":"crossref","unstructured":"Ery Arias-Castro, Emmanuel J Cand\u00e8s, and Arnaud Durand. Detection of an anomalous cluster in a network. The Annals of Statistics, 39(1):278\u2013304, 2011.","DOI":"10.1214\/10-AOS839"},{"key":"9215_CR7","doi-asserted-by":"crossref","unstructured":"Ery Arias-Castro, David\u00a0L Donoho, and Xiaoming Huo. Near-optimal detection of geometric objects by fast multiscale methods. Information Theory, IEEE Transactions on, 51(7):2402\u20132425, 2005.","DOI":"10.1109\/TIT.2005.850056"},{"key":"9215_CR8","doi-asserted-by":"crossref","unstructured":"M. Bayati and A. Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Trans. on Inform. Theory, 57:764\u2013785, 2011.","DOI":"10.1109\/TIT.2010.2094817"},{"key":"9215_CR9","unstructured":"Mohsen Bayati, Marc Lelarge, and Andrea Montanari. Universality in polytope phase transitions and message passing algorithms. arXiv preprint arXiv:1207.7321 , 2012."},{"key":"9215_CR10","unstructured":"Quentin Berthet and Philippe Rigollet. Computational lower bounds for sparse pca. arXiv preprint arXiv:1304.0828 , 2013."},{"key":"9215_CR11","unstructured":"Shankar Bhamidi, Partha S Dey, and Andrew B Nobel. Energy landscape for large average submatrix detection problems in gaussian random matrices. arXiv preprint arXiv:1211.2284 , 2012."},{"key":"9215_CR12","unstructured":"Patrick Billingsley. Probability and measure. John Wiley & Sons, 2008."},{"key":"9215_CR13","doi-asserted-by":"crossref","unstructured":"Emmanuel\u00a0J Cand\u00e8s, Xiaodong Li, Yi\u00a0Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):11, 2011.","DOI":"10.1145\/1970392.1970395"},{"key":"9215_CR14","unstructured":"Alexandre d\u2019Aspremont, Francis Bach, and Laurent El Ghaoui. Optimal solutions for sparse principal component analysis. The Journal of Machine Learning Research, 9:1269\u20131294, 2008."},{"key":"9215_CR15","doi-asserted-by":"crossref","unstructured":"Alexandre d\u2019Aspremont, Laurent El Ghaoui, Michael I Jordan, and Gert RG Lanckriet. A direct formulation for sparse pca using semidefinite programming. SIAM review, 49(3):434\u2013448, 2007.","DOI":"10.1137\/050645506"},{"key":"9215_CR16","doi-asserted-by":"crossref","unstructured":"Chandler Davis and W. M. Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):pp. 1\u201346, 1970.","DOI":"10.1137\/0707001"},{"key":"9215_CR17","doi-asserted-by":"crossref","unstructured":"Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres. Finding hidden cliques in linear time with high probability. In ANALCO, pages 67\u201375. SIAM, 2011.","DOI":"10.1137\/1.9781611973013.8"},{"key":"9215_CR18","unstructured":"Amir Dembo. Probability Theory. http:\/\/www.stanford.edu\/~montanar\/TEACHING\/Stat310A\/lnotes.pdf , 2013."},{"key":"9215_CR19","doi-asserted-by":"crossref","unstructured":"David\u00a0L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914\u201318919, 2009.","DOI":"10.1073\/pnas.0909892106"},{"key":"9215_CR20","doi-asserted-by":"crossref","unstructured":"Uriel Feige and Dorit Ron. Finding hidden cliques in linear time. DMTCS Proceedings, (01):189\u2013204, 2010.","DOI":"10.46298\/dmtcs.2802"},{"key":"9215_CR21","unstructured":"Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. Statistical algorithms and a lower bound for planted clique. arXiv preprint arXiv:1201.1214 , 2012."},{"key":"9215_CR22","doi-asserted-by":"crossref","unstructured":"Zolt\u00e1n F\u00fcredi and J\u00e1nos Koml\u00f3s. The eigenvalues of random symmetric matrices. Combinatorica, 1(3):233\u2013241, 1981.","DOI":"10.1007\/BF02579329"},{"key":"9215_CR23","doi-asserted-by":"crossref","unstructured":"Geoffrey R Grimmett and Colin JH McDiarmid. On colouring random graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 77, pages 313\u2013324. Cambridge Univ Press, 1975.","DOI":"10.1017\/S0305004100051124"},{"key":"9215_CR24","doi-asserted-by":"crossref","unstructured":"Dongning Guo and Chih-Chun Wang. Asymptotic mean-square optimality of belief propagation for sparse linear systems. In Information Theory Workshop, 2006. ITW\u201906 Chengdu. IEEE, pages 194\u2013198. IEEE, 2006.","DOI":"10.1109\/ITW2.2006.323786"},{"key":"9215_CR25","doi-asserted-by":"crossref","unstructured":"Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, 3(4):347\u2013359, 1992.","DOI":"10.1002\/rsa.3240030402"},{"key":"9215_CR26","doi-asserted-by":"crossref","unstructured":"Iain M Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis in high dimensions. Journal of the American Statistical Association, 104(486), 2009.","DOI":"10.1198\/jasa.2009.0121"},{"key":"9215_CR27","unstructured":"Antti Knowles and Jun Yin. The isotropic semicircle law and deformation of wigner matrices. arXiv preprint arXiv:1110.6449 , 2011."},{"key":"9215_CR28","unstructured":"Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009."},{"key":"9215_CR29","doi-asserted-by":"crossref","unstructured":"Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193\u2013201, 1992.","DOI":"10.1137\/0221015"},{"key":"9215_CR30","doi-asserted-by":"crossref","unstructured":"Marc Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"9215_CR31","doi-asserted-by":"crossref","unstructured":"Andrea Montanari. Graphical Models Concepts in Compressed Sensing. In Y.C. Eldar and G. Kutyniok, editors, Compressed Sensing: Theory and Applications. Cambridge University Press, 2012.","DOI":"10.1017\/CBO9780511794308.010"},{"key":"9215_CR32","doi-asserted-by":"crossref","unstructured":"Andrea Montanari and David Tse. Analysis of belief propagation for non-linear problems: The example of cdma (or: How to prove tanaka\u2019s formula). In Information Theory Workshop, 2006. ITW\u201906 Punta del Este. IEEE, pages 160\u2013164. IEEE, 2006.","DOI":"10.1109\/ITW.2006.1633802"},{"key":"9215_CR33","doi-asserted-by":"crossref","unstructured":"Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259\u20131277, 1995.","DOI":"10.1137\/S0097539793254571"},{"key":"9215_CR34","doi-asserted-by":"crossref","unstructured":"Sundeep Rangan and Alyson K Fletcher. Iterative estimation of constrained rank-one matrices in noise. In Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, pages 1246\u20131250. IEEE, 2012.","DOI":"10.1109\/ISIT.2012.6283056"},{"key":"9215_CR35","doi-asserted-by":"crossref","unstructured":"Tom Richardson and R\u00fcdiger Leo Urbanke. Modern coding theory. Cambridge University Press, 2008.","DOI":"10.1017\/CBO9780511791338"},{"key":"9215_CR36","doi-asserted-by":"crossref","unstructured":"Andrey A Shabalin, Victor J Weigman, Charles M Perou, and Andrew B Nobel. Finding large average submatrices in high dimensional data. The Annals of Applied Statistics, pages 985\u20131012, 2009.","DOI":"10.1214\/09-AOAS239"},{"key":"9215_CR37","unstructured":"Xing Sun and Andrew B Nobel. On the size and recovery of submatrices of ones in a random binary matrix. J. Mach. Learn. Res, 9:2431\u20132453, 2008."},{"key":"9215_CR38","doi-asserted-by":"crossref","unstructured":"Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):24, 2013.","DOI":"10.1145\/2431211.2431223"},{"key":"9215_CR39","doi-asserted-by":"crossref","unstructured":"Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Y.C. Eldar and G. Kutyniok, editors, Compressed Sensing: Theory and Applications, pages 210\u2013268. Cambridge University Press, 2012.","DOI":"10.1017\/CBO9780511794308.006"},{"key":"9215_CR40","doi-asserted-by":"crossref","unstructured":"Martin J Wainwright and Michael I Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1\u20132):1\u2013305, 2008.","DOI":"10.1561\/2200000001"},{"key":"9215_CR41","doi-asserted-by":"crossref","unstructured":"Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of computational and graphical statistics, 15(2):265\u2013286, 2006.","DOI":"10.1198\/106186006X113430"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9215-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-014-9215-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9215-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T14:44:22Z","timestamp":1746369862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-014-9215-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,9]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9215"],"URL":"https:\/\/doi.org\/10.1007\/s10208-014-9215-y","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,9]]}}}