Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem
summary
Proves NP-hardness of approximating the (bilinear) Grothendieck problem strictly beyond the PSD bound: shows no polytime algorithm achieves better than π/2 + 10^{-6} (unoptimized ε) unless P=NP. Reduction embeds label cover into an operator A = F1^T P F1 − λI, uses Boolean Fourier/dictator tests, projection to label-cover subspace, and a global geometric analysis (win–win distance lemmas, sign/sine rounding) to convert SDP integrality-gap style instances to NP-hardness.
AI-written summary · about