Towards computing the Grothendieck constant

with Prasad Raghavendra. SODA 2009.

PDF

abstract

The Grothendieck constant $K_G$ is the smallest constant such that for every $d\in \mathbb{N}$ and every matrix $A = (a_{ij})$, $$\sup_{\vec u_i,\vec v_j \in B^{(d)}} \sum_{ij} a_{ij} \langle \vec u_i , \vec v_j\rangle \leq K_G \cdot \sup_{x_i,y_j \in [-1,1]} \sum_{ij} a_{ij} x_i y_j \, ,$$ where $B^{(d)}$ is the unit ball in $\mathbb{R}^d$. Despite several efforts [Krivine, Reeds], the value of the constant $K_G$ remains unknown.

The Grothendieck constant $K_G$ is precisely the integrality gap of a natural SDP relaxation for the Bipartite Quadratic Programming problem. The input to this problem is a matrix $A = (a_{ij})$ and the objective is to maximize the quadratic form $\sum_{ij} a_{ij} x_i y_j$ over $x_i, y_j \in [-1,1]$.

In this work, we apply techniques from [Raghavendra'08] to the Bipartite Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [Raghavendra'08] yields the following hardness result: Assuming the Unique Games Conjecture, it is NP-hard to approximate the Bipartite Quadratic Programming problem to any factor better than the Grothendieck constant $K_G$.

By adapting a “bootstrapping” argument used in a proof of Grothendieck inequality, we are able to perform a tighter analysis than [Raghavendra'08]. Through this careful analysis, we obtain the following new results:

• An approximation algorithm for Bipartite Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant $K_G$ (optimal approximation ratio assuming the Unique Games Conjecture).

• We show that the Grothendieck constant $K_G$ can be computed within an error $\eta$, in time depending only on $\eta$. Specifically, for each $\eta$, we formulate an explicit finite linear program, whose optimum is $\eta$-close to the Grothendieck constant.

We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.

keywords

• approximation algorithms
• semidefinite programming
• hardness reduction