Computer Science/Discrete Mathematics Seminar II

We study the following problem regarding quadratic programs: Given a quadratic polynomial \sum a_{xy} xy, where all a_{xx} = 0, find a -1,+1 assignment to its variables that maximizes it. This problem recently attracted attention due to its application in various clustering settings [Charikar and Wirth, 2004] as well as an intriguing connection to the famous Grothendieck inequality [Alon and Naor, 2004]. It can be approximated to within a factor of $O(\log n)$ [Nesterov, Nemirovski], and known to be NP-hard to approximate to within any factor better than 13/11 [Charikar, Wirth]. We show it is quasi-NP-hard to approximate this sum to within a factor of O(\log^\gamma n). The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be $\Theta(\log n)$ [Alon, Makarychev^2, Naor]. We give an explicit instance for which the integrality gap is \Omega(\log n / \log \log n), essentially answering the main open problem of [Alon, Makarychev^2, Naor].