The Grothendieck Constant is Strictly Smaller than Krivine's Bound
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor · 2011
The classical Grothendieck constant, denoted KG, is equal to the integrality gap of the natural semidefinite relaxation of the problem of computing max {Σi-1mΣj=1naijεiδj: {εi}i=1m, {δj}j=1n⊆{-1,1} } a generic and well-studied optimization problem with many applications. Krivine proved in 1977 that KG ≤ 2log (1+√2)/π and conjectured that his estimate is sharp. We obtain a sharper Grothendieck inequality, showing that KGo>; 0. Our main contribution is conceptual: despite dealing with a binary rounding problem, random 2-dimensional projections combined with a careful partition of ℝ2in order to round the projected vectors, beat the random hyperplane technique, contrary to Krivine's long-standing conjecture.