Towards computing the Grothendieck constant

with Prasad Raghavendra. SODA 2009.



The Grothendieck constant KGK_G is the smallest constant such that for every dNd\in \mathbb{N} and every matrix A=(aij)A = (a_{ij}), supui,vjB(d)ijaijui,vjKGsupxi,yj[1,1]ijaijxiyj,\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)B^{(d)} is the unit ball in Rd\mathbb{R}^d. Despite several efforts [Krivine, Reeds], the value of the constant KGK_G remains unknown.

The Grothendieck constant KGK_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=(aij)A = (a_{ij}) and the objective is to maximize the quadratic form ijaijxiyj\sum_{ij} a_{ij} x_i y_j over xi,yj[1,1]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 KGK_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 KGK_G (optimal approximation ratio assuming the Unique Games Conjecture).

  • We show that the Grothendieck constant KGK_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.


  • approximation algorithms
  • semidefinite programming
  • hardness reduction