Towards computing the Grothendieck constant
with Prasad Raghavendra. SODA 2009.
The Grothendieck constant is the smallest constant such that for every and every matrix , where is the unit ball in . Despite several efforts [Krivine, Reeds], the value of the constant remains unknown.
The Grothendieck constant is precisely the integrality gap of a natural SDP relaxation for the Bipartite Quadratic Programming problem. The input to this problem is a matrix and the objective is to maximize the quadratic form over .
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 .
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 (optimal approximation ratio assuming the Unique Games Conjecture).
We show that the Grothendieck constant can be computed within an error , in time depending only on . Specifically, for each , we formulate an explicit finite linear program, whose optimum is -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