About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 2011
Conference paper
The Grothendieck constant is strictly smaller than Krivine's bound
Abstract
The classical Grothendieck constant, denoted K G, is equal to the integrality gap of the natural semi definite relaxation of the problem of computing (Equation Presented), a generic and well-studied optimization problem with many applications. Krivine proved in 1977 that K G ≤ π/2 log(1+√2) and conjectured that his estimate is sharp. We obtain a sharper Grothendieck inequality, showing that K G < π/2 log(1+√2)-ε 0 for an explicit constant ε 0 > 0. Our main contribution is conceptual: despite dealing with a binary rounding problem, random 2-dimensional projections combined with a careful partition of ℝ 2 in order to round the projected vectors, beat the random hyper plane technique, contrary to Krivine's long-standing conjecture. © 2011 IEEE.