{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:29:21Z","timestamp":1786980561980,"version":"build-2736575974"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,11,17]],"date-time":"2016-11-17T00:00:00Z","timestamp":1479340800000},"content-version":"unspecified","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":[[2018,4]]},"DOI":"10.1007\/s10208-016-9341-9","type":"journal-article","created":{"date-parts":[[2016,11,17]],"date-time":"2016-11-17T14:46:09Z","timestamp":1479393969000},"page":"345-379","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":48,"title":["Random Laplacian Matrices and Convex Relaxations"],"prefix":"10.1007","volume":"18","author":[{"given":"Afonso S.","family":"Bandeira","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,11,17]]},"reference":[{"issue":"1","key":"9341_CR1","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1109\/TNSE.2014.2368716","volume":"1","author":"E Abbe","year":"2014","unstructured":"E.\u00a0Abbe, A.\u00a0S. Bandeira, A.\u00a0Bracher, and A.\u00a0Singer. Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. Network Science and Engineering, IEEE Transactions on, 1(1):10\u201322, Jan 2014.","journal-title":"Network Science and Engineering, IEEE Transactions on"},{"key":"9341_CR2","doi-asserted-by":"crossref","unstructured":"E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer. Linear inverse problems on Erd\u0151s-R\u00e9nyi graphs: Information-theoretic limits and efficient recovery. IEEE International Symposium on Information Theory (ISIT2014), 2014.","DOI":"10.1109\/ISIT.2014.6875033"},{"key":"9341_CR3","unstructured":"E. Abbe, A. . Bandeira, and G. Hall. Exact recovery in the stochastic block model. Available online at arXiv:1405.3267v4 [cs.SI], 2014."},{"key":"9341_CR4","unstructured":"N. Agarwal, A.\u00a0S. Bandeira, K.\u00a0Koiliaris, and A.\u00a0Kolla. Multisection in the stochastic block model using semidefinite programming. Available online at arXiv:1507.02323 [cs.DS], 2015."},{"key":"9341_CR5","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F Alizadeh","year":"1993","unstructured":"F.\u00a0Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5:13\u201351, 1993.","journal-title":"SIAM Journal on Optimization"},{"key":"9341_CR6","series-title":"Cambridge studies in advanced mathematics","volume-title":"An introduction to random matrices","author":"GW Anderson","year":"2010","unstructured":"G.\u00a0W. Anderson, A.\u00a0Guionnet, and O.\u00a0Zeitouni. An introduction to random matrices. Cambridge studies in advanced mathematics. Cambridge University Press, Cambridge, New York, Melbourne, 2010."},{"key":"9341_CR7","unstructured":"A. S. Bandeira, N. Boumal, and A. Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Available online at arXiv:1411.3272 [math.OC], 2014."},{"key":"9341_CR8","unstructured":"A.\u00a0S. Bandeira, Y.\u00a0Khoo, and A.\u00a0Singer. Open problem: Tightness of maximum likelihood semidefinite relaxations. In Proceedings of the 27th Conference on Learning Theory, volume\u00a035 of JMLR W&CP, pages 1265\u20131267, 2014."},{"issue":"4","key":"9341_CR9","doi-asserted-by":"crossref","first-page":"1611","DOI":"10.1137\/120875338","volume":"34","author":"AS Bandeira","year":"2013","unstructured":"A.\u00a0S. Bandeira, A.\u00a0Singer, and D.\u00a0A. Spielman. A Cheeger inequality for the graph connection Laplacian. SIAM J. Matrix Anal. Appl., 34(4):1611\u20131630, 2013.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9341_CR10","doi-asserted-by":"crossref","unstructured":"A.\u00a0S. Bandeira and R.\u00a0v.\u00a0Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Annals of Probability, to appear, 2015.","DOI":"10.1214\/15-AOP1025"},{"issue":"1\u20133","key":"9341_CR11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"N.\u00a0Bansal, A.\u00a0Blum, and S.\u00a0Chawla. Correlation clustering. Machine Learning, 56(1-3):89\u2013113, 2004.","journal-title":"Machine Learning"},{"key":"9341_CR12","doi-asserted-by":"crossref","unstructured":"R.\u00a0B. Boppana. Eigenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium on Foundations of Computer Science, pages 280\u2013285, 1987.","DOI":"10.1109\/SFCS.1987.22"},{"issue":"2","key":"9341_CR13","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1214\/009117904000000856","volume":"33","author":"S Boucheron","year":"2005","unstructured":"S.\u00a0Boucheron, O.\u00a0Bousquet, G.\u00a0Lugosi, and P.\u00a0Massart. Moment inequalities for functions of independent random variables. Ann. Probab., 33(2):514\u2013560, 2005.","journal-title":"Ann. Probab."},{"issue":"1","key":"9341_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/009117905000000495","volume":"34","author":"W Bryc","year":"2006","unstructured":"W.\u00a0Bryc, A.\u00a0Dembo, and T.\u00a0Jiang. Spectral measure of large random Hankel, Markov and Toeplitz matrices. The Annals of Probability, 34(1):pp. 1\u201338, 2006.","journal-title":"The Annals of Probability"},{"key":"9341_CR15","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Chen and A.\u00a0J. Goldsmith. Information recovery from pairwise measurements. IEEE International Symposium on Information Theory (ISIT2014), 2014.","DOI":"10.1109\/ISIT.2014.6875186"},{"key":"9341_CR16","unstructured":"Y.\u00a0Chen, C.\u00a0Suh, and A.\u00a0J. Goldsmith. Information recovery from pairwise measurements: A Shannon-theoretic approach. Available online at arXiv:1504.01369 [cs.IT], 2015."},{"key":"9341_CR17","volume-title":"Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics)","author":"F Chung","year":"2006","unstructured":"F.\u00a0Chung and L.\u00a0Lu. Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics). American Mathematical Society, Boston, MA, USA, 2006."},{"key":"9341_CR18","doi-asserted-by":"crossref","unstructured":"F.\u00a0R.\u00a0K. Chung. Spectral Graph Theory. AMS, 1997.","DOI":"10.1090\/cbms\/092"},{"key":"9341_CR19","doi-asserted-by":"crossref","unstructured":"M.\u00a0Cucuringu. Synchronization over Z2 and community detection in signed multiplex networks with constraints. Journal of Complex Networks, 2015.","DOI":"10.1093\/comnet\/cnu050"},{"key":"9341_CR20","doi-asserted-by":"crossref","unstructured":"K.\u00a0Davidson and S.\u00a0Szarek. Local operator theory, random matrices and Banach spaces. In Handbook on the Geometry of Banach spaces, volume\u00a01, pages 317\u2013366. Elsevier Science, 2001.","DOI":"10.1016\/S1874-5849(01)80010-3"},{"key":"9341_CR21","doi-asserted-by":"crossref","unstructured":"A.\u00a0Decelle, F.\u00a0Krzakala, C.\u00a0Moore, and L.\u00a0Zdeborov\u00e1. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E, 84, December 2011.","DOI":"10.1103\/PhysRevE.84.066106"},{"issue":"6","key":"9341_CR22","doi-asserted-by":"crossref","first-page":"2086","DOI":"10.1214\/10-AAP677","volume":"20","author":"X Ding","year":"2010","unstructured":"X.\u00a0Ding and T.\u00a0Jiang. Spectral distribution of adjacency and Laplacian matrices of random graphs. The Annals of Applied Probability, 20(6):2086\u20132117, 2010.","journal-title":"The Annals of Applied Probability"},{"key":"9341_CR23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546594","volume-title":"Random Graph Dynamics (Cambridge Series in Statistical and Probabilistic Mathematics)","author":"R Durrett","year":"2006","unstructured":"R.\u00a0Durrett. Random Graph Dynamics (Cambridge Series in Statistical and Probabilistic Mathematics). Cambridge University Press, New York, NY, USA, 2006."},{"key":"9341_CR24","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"P.\u00a0Erd\u0151s and A.\u00a0R\u00e9nyi. On random graphs, I. Publicationes Mathematicae (Debrecen), 6:290\u2013297, 1959.","journal-title":"I. Publicationes Mathematicae (Debrecen)"},{"issue":"4","key":"9341_CR25","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1006\/jcss.2001.1773","volume":"63","author":"U Feige","year":"2001","unstructured":"U.\u00a0Feige and J.\u00a0Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639 \u2013 671, 2001.","journal-title":"Journal of Computer and System Sciences"},{"key":"9341_CR26","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"M.\u00a0X. Goemans and D.\u00a0P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefine programming. Journal of the Association for Computing Machinery, 42:1115\u20131145, 1995.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"2","key":"9341_CR27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"M.\u00a0Gr\u00f6tschel, L.\u00a0Lov\u00e1sz, and A.\u00a0Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169\u2013197, 1981.","journal-title":"Combinatorica"},{"key":"9341_CR28","unstructured":"B.\u00a0Hajek, Y.\u00a0Wu, and J.\u00a0Xu. Achieving exact cluster recovery threshold via semidefinite programming. Available online at arXiv:1412.6156 , 2014."},{"key":"9341_CR29","unstructured":"B.\u00a0Hajek, Y.\u00a0Wu, and J.\u00a0Xu. Achieving exact cluster recovery threshold via semidefinite programming: Extensions. Available online at arXiv:1502.07738 , 2015."},{"key":"9341_CR30","doi-asserted-by":"crossref","unstructured":"S.\u00a0Khot. On the power of unique 2-prover 1-round games. Thiry-fourth annual ACM symposium on Theory of computing, 2002.","DOI":"10.1145\/510014.510017"},{"key":"9341_CR31","unstructured":"M.\u00a0Ledoux and M.\u00a0Talagrand. Probability in Banach spaces, volume\u00a023 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991."},{"issue":"1","key":"9341_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lovasz","year":"1979","unstructured":"L.\u00a0Lovasz. On the shannon capacity of a graph. IEEE Trans. Inf. Theor., 25(1):1\u20137, 1979.","journal-title":"IEEE Trans. Inf. Theor."},{"key":"9341_CR33","doi-asserted-by":"crossref","unstructured":"P.\u00a0Massart. About the constants in Talagrand\u2019s concentration inequalities for empirical processes. The Annals of Probability, 28(2), 2000.","DOI":"10.1214\/aop\/1019160263"},{"key":"9341_CR34","doi-asserted-by":"crossref","unstructured":"L.\u00a0Massouli\u00e9. Community detection thresholds and the weak Ramanujan property. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC \u201914, pages 694\u2013703, New York, NY, USA, 2014. ACM.","DOI":"10.1145\/2591796.2591857"},{"key":"9341_CR35","unstructured":"F.\u00a0McSherry. Spectral partitioning of random graphs."},{"key":"9341_CR36","unstructured":"E.\u00a0Mossel, J.\u00a0Neeman, and A.\u00a0Sly. Consistency thresholds for the planted bisection model. Available online at arXiv:1407.1591v2 [math.PR], July 2014."},{"key":"9341_CR37","unstructured":"E.\u00a0Mossel, J.\u00a0Neeman, and A.\u00a0Sly. A proof of the block model threshold conjecture. Available online at arXiv:1311.4115 [math.PR], January 2014."},{"key":"9341_CR38","unstructured":"E.\u00a0Mossel, J.\u00a0Neeman, and A.\u00a0Sly. Stochastic block models and reconstruction. Probability Theory and Related Fields (to appear), 2014."},{"key":"9341_CR39","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Nesterov and A.\u00a0Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"9341_CR40","doi-asserted-by":"crossref","unstructured":"P.\u00a0Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC \u201908, pages 245\u2013254. ACM, 2008.","DOI":"10.1145\/1374376.1374414"},{"issue":"3","key":"9341_CR41","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"S.\u00a0Sahni and T.\u00a0Gonzalez. P-complete approximation problems. J. ACM, 23(3):555\u2013565, July 1976.","journal-title":"J. ACM"},{"issue":"1","key":"9341_CR42","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.acha.2010.02.001","volume":"30","author":"A Singer","year":"2011","unstructured":"A.\u00a0Singer. Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmon. Anal., 30(1):20 \u2013 36, 2011.","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9341_CR43","doi-asserted-by":"crossref","unstructured":"T.\u00a0Tao. Topics in Random Matrix Theory. Graduate studies in mathematics. American Mathematical Soc., 2012.","DOI":"10.1090\/gsm\/132"},{"issue":"4","key":"9341_CR44","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","volume":"12","author":"JA Tropp","year":"2012","unstructured":"J.\u00a0A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389\u2013434, 2012.","journal-title":"Foundations of Computational Mathematics"},{"issue":"1\u20132","key":"9341_CR45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000048","volume":"8","author":"JA Tropp","year":"2015","unstructured":"J.\u00a0A. Tropp. An introduction to matrix concentration inequalities. Found. Trends Mach. Learning, 8(1\u20132):1\u2013230, 2015.","journal-title":"Found. Trends Mach. Learning"},{"key":"9341_CR46","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vanderberghe","year":"1996","unstructured":"L.\u00a0Vanderberghe and S.\u00a0Boyd. Semidefinite programming. SIAM Review, 38:49\u201395, 1996.","journal-title":"SIAM Review"},{"key":"9341_CR47","doi-asserted-by":"crossref","unstructured":"R.\u00a0Vershynin. Introduction to the non-asymptotic analysis of random matrices. Chapter 5 of: Compressed Sensing, Theory and Applications. Edited by Y. Eldar and G. Kutyniok. Cambridge University Press, 2012.","DOI":"10.1017\/CBO9780511794308.006"},{"issue":"2","key":"9341_CR48","doi-asserted-by":"crossref","first-page":"325","DOI":"10.2307\/1970008","volume":"67","author":"EP Wigner","year":"1958","unstructured":"E.\u00a0P. Wigner. On the distribution of the roots of certain symmetric matrices. Annals of Mathematics, 67(2):pp. 325\u2013327, 1958.","journal-title":"Annals of Mathematics"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-016-9341-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-016-9341-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-016-9341-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T19:39:26Z","timestamp":1692560366000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-016-9341-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,17]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9341"],"URL":"https:\/\/doi.org\/10.1007\/s10208-016-9341-9","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,17]]}}}