Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality

J Kuczyński and H Woźniakowski, Estimating the largest eigenvalue by the power and lanczos algorithms with a random start , SIAM journal on matrix analysis and applications 13

1992

Earlier work this paper cites.

Alexander I. Barvinok, Problems of distance geometry and convex properties of quadratic maps , Discrete & Computational Geometry 13

1995

Earlier work this paper cites.

Michel X Goemans and David P Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , Journal of the ACM (JACM) 42

1995

Earlier work this paper cites.

Alexander Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques , Resenhas do Instituto de Matemática e Estatística da Universidade de São Paulo 2

1996

Earlier work this paper cites.

Gábor Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues , Mathematics of operations research 23

1998

Earlier work this paper cites.

Iain M Johnstone, On the distribution of the largest eigenvalue in principal components analysis , Annals of statistics (2001), 295–327

2001

Earlier work this paper cites.

Samuel Burer and Renato DC Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization , Mathematical Programming 95

2003

Earlier work this paper cites.

Joel Friedman, A proof of alon’s second eigenvalue conjecture , Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, 2003, pp. 720–724

2003

Earlier work this paper cites.

Sanjeev Arora, Elad Hazan, and Satyen Kale, Fast algorithms for approximate semidefinite programming using the multiplicative weights update method , Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, IEEE, 2005, pp. 339–348

2005

Earlier work this paper cites.

Jinho Baik, Gérard Ben Arous, Sandrine Péché, et al., Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices , The Annals of Probability 33

2005

Earlier work this paper cites.

P-A Absil, Christopher G Baker, and Kyle A Gallivan, Trust-region methods on Riemannian manifolds , Foundations of Computational Mathematics 7

2007

Earlier work this paper cites.

Sanjeev Arora and Satyen Kale, A combinatorial, primal-dual approach to semidefinite programs , Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, ACM, 2007, pp. 227–236

2007

Earlier work this paper cites.

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for max-cut and other 2-variable csps? , SIAM Journal on Computing 37

2007

Cited alongside, same era.

Satish Babu Korada and Nicolas Macris, Exact solution of the gauge symmetric p-spin glass model on a complete graph , Journal of Statistical Physics 136

2009

Cited alongside, same era.

Greg W Anderson, Alice Guionnet, and Ofer Zeitouni, An introduction to random matrices , vol. 118, Cambridge university press, 2010

2010

Cited alongside, same era.

David Steurer, Fast sdp algorithms for constraint satisfaction problems , Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 2010, pp. 684–697

Original

2010

Cited alongside, same era.

Dan Garber and Elad Hazan, Approximating semidefinite programs in sublinear time , Advances in Neural Information Processing Systems, 2011, pp. 1080–1088

Laurent Massoulié, Community detection thresholds and the weak ramanujan property , Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, 2014, pp. 694–703

2014

Later among the works it cites.

Nicolas Boumal, A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints , arXiv:1506.00575

Original

2015

Later among the works it cites.

Yash Deshpande, Emmanuel Abbe, and Andrea Montanari, Asymptotic mutual information for the two-groups stochastic block model , arXiv preprint arXiv:1507.08685 (2015)

Original

2015

Later among the works it cites.

Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall, Exact recovery in the stochastic block model , IEEE Transactions on Information Theory 62

2016

Later among the works it cites.

Afonso S Bandeira, Nicolas Boumal, and Vladislav Voroninski, On the low-rank approach for semidefinite programs arising in synchronization and community detection , arXiv preprint arXiv:1602.04426 (2016)