A Grothendieck-type inequality for local maxima

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.

Yuri Nesterov, Semidefinite relaxation and nonconvex quadratic optimization , Optimization methods and software 9

1998

Earlier work this paper cites.

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

2003

Earlier work this paper cites.

Michel Journée, Francis Bach, P-A Absil, and Rodolphe Sepulchre, Low-rank optimization on the cone of positive semidefinite matrices , SIAM Journal on Optimization 20

2010

Earlier work this paper cites.

Po-Ling Loh and Martin J Wainwright, High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity , Advances in Neural Information Processing Systems, 2011, pp. 2726–2734

2011

Cited alongside, same era.

Subhash Khot and Assaf Naor, Grothendieck-type inequalities in combinatorial optimization , Communications on Pure and Applied Mathematics 65

2012

Cited alongside, same era.

Yuxin Chen and Emmanuel Candes, Solving random quadratic systems of equations is nearly as easy as solving linear systems , Advances in Neural Information Processing Systems, 2015, pp. 739–747

2015

Cited alongside, same era.

Olivier Guédon and Roman Vershynin, Community detection in sparse networks via grothendieck’s inequality , Probability Theory and Related Fields (2015), 1–25

2015

Cited alongside, same era.

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

Original

2016

Closest in time.

Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi, Phase transitions in semidefinite relaxations , Proceedings of the National Academy of Sciences (2016), In press

2016

Closest in time.

Andrea Montanari and Subhabrata Sen, Semidefinite programs on sparse random graphs and their application to community detection , Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, 2016

2016

Closest in time.

Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh, Matrix completion from noisy entries , Journal of Machine Learning Research 11

2078

Closest in time.