The Grothendieck constant is strictly smaller than Krivine's bound

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Pages453-462
Number of pages10
DOIs
StatePublished - 2011
Event2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States
Duration: Oct 22 2011Oct 25 2011

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
CountryUnited States
CityPalm Springs, CA
Period10/22/1110/25/11

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Braverman, M., Makarychev, K., Makarychev, Y., & Naor, A. (2011). The Grothendieck constant is strictly smaller than Krivine's bound. In Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 (pp. 453-462). [6108206] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2011.77