This paper studies the computational complexity of the following type of
quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. 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 {\em Grothendieck inequality} (Alon and Naor, 2004). It is approximable to within a factor of $O(\log n)$~\cite{nesterov,nemirovski,megretski,tony}, and known to be NP-hard to approximate within any factor better than $13/11 -\epsilon$ for all $\epsilon >0$~\cite{tony}. We show that it is quasi-NP-hard to approximate to a factor better than $O(\log^\gamma n)$ for some $\gamma>0$.

The integrality gap of the natural semidefinite relaxation for this problem is known as the {\em Grothendieck constant} of the complete graph, and known to be $\Theta(\log n)$ (Alon, K. Makarychev, Y. Makarychev and Naor, 2005~\cite{alonQP}). The proof of this fact was {\em nonconstructive}, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is $\Omega(\frac{\log n}{\log \log n})$, essentially answering one of the open problems of \cite{alonQP}.