2011/10/01 by Mark Braverman, Konstantin Makarychev, Yury Makarychev +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Stochastic Gradient Optimization Techniques #Computer science
paper · doi:10.1109/focs.2011.77
openalex publication_date 2011/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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: εii=1m, δjj=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.