Theory of Computing
-------------------
Title : Grothendieck Inequalities for Semidefinite Programs with Rank Constraint
Authors : Jop Briet, Fernando Mario de Oliveira Filho, and Frank Vallentin
Volume : 10
Number : 4
Pages : 77-105
URL : http://www.theoryofcomputing.org/articles/v010a004
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 constraint 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.