TY - GEN

T1 - The Grothendieck constant is strictly smaller than Krivine's bound

AU - Braverman, Mark

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Naor, Assaf

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84863320888&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863320888&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2011.77

DO - 10.1109/FOCS.2011.77

M3 - Conference contribution

AN - SCOPUS:84863320888

SN - 9780769545714

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 453

EP - 462

BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

Y2 - 22 October 2011 through 25 October 2011

ER -