Grothendieck inequalities for semidefinite programs with rank constraint

Abstract

Grothendieck inequalities are fundamental inequalities which are frequently used in many areas of mathematics and computer science. They can be interpreted as upper bounds for the integrality gap between two optimization problems: a difficult semidefinite program with rank-1 constraint and its easy semidefinite relaxation where the rank constrained is dropped. For instance, the integrality gap of the Goemans-Williamson approximation algorithm for MAX CUT can be seen as a Grothendieck inequality. In this paper we consider Grothendieck inequalities for ranks greater than 1 and we give two applications: approximating ground states in the n-vector model in statistical mechanics and XOR games in quantum information theory.

22 pages

References in corpus (3)

• A generalized Grothendieck inequality and entanglement in XOR games
• The Grothendieck constant is strictly smaller than Krivine's bound
• Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Cited by in corpus (7)

• Distributed Maximum Likelihood Sensor Network Localization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• An Improved Approximation Algorithm for Quantum Max-Cut
• Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups
• Complexity of the positive semidefinite matrix completion problem with a rank constraint
• Better bounds on finite-order Grothendieck constants