Symmetric Grothendieck Inequality

We show that the

* Goemans-Williamson inequality and rank-constrained positive semidefinite Grothendieck inequality in Theoretical Computer Science,

* Nesterov \pi/2-Theorem and Ben-Tal-Nemirovski-Roos 4/\pi-Theorem in Optimization,

* generalized Grothendieck inequality and order-p Grothendieck inequality in Quantum Information Theory,

as well as the celebrated Grothendieck inequality itself, are all special cases of an inequality relating a pair of norms over a convex cone of symmetric matrices. We call this the symmetric Grothendieck inequality. It brings new insights to old results: The polynomial-time solvability of rank-constrained SDP when rank is large enough (due to Barvinok and Pataki), the convex relaxation bounds for binary QPs (of Megretski and Charikar-Wirth) may be deduced or extended in light of this new inequality. This is joint work with Shmuel Friedland.