The grothendieck constant is strictly smaller than krivine's bound

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

The (real) Grothendieck constant KG is the infimum over those K ∈ (0, ∞) such that for every m, n ∈ N and every m × n real matrix (aij) we have max -xi}m i=1, -yj}n j=1 ⊆ Sn+m-1 Σm i=1 Σm j=1 aij(xi, yj) ≤ K -ϵi}m i=1, -δj}max n j=1 ⊆-1, 1} Σm i=1 Σm j=1aijϵiδj. The classical Grothendieck inequality asserts the nonobvious fact that the above inequality does hold true for some K ∈ (0, ∞) that is independent of m; n and (aij). Since Grothendieck's 1953 discovery of this powerful theorem, it has found numerous applications in a variety of areas, but, despite attracting a lot of attention, the exact value of the Grothendieck constant KG remains a mystery. The last progress on this problem was in 1977, when Krivine proved that KG ≤ π/2log(1 + √2) and conjectured that his bound is optimal. Krivine's conjecture has been restated repeatedly since 1977, resulting in focusing the subsequent research on the search for examples of matrices (aij) which exhibit (asymptotically, as m; n → ∞) a lower bound on KG that matches Krivine's bound. Here, we obtain an improved Grothendieck inequality that holds for all matrices (aij) and yields a bound KG < π/2 log(1 + √2) - ϵ0 for some effective constant ϵ0 > 0. Other than disproving Krivine's conjecture, and along the way also disproving an intermediate conjecture of König that was made in 2000 as a step towards Krivine's conjecture, our main contribution is conceptual: despite dealing with a binary rounding problem, random two-dimensional projections, when combined with a careful partition of R2 in order to round the projected vectors to values in -1, 1}, perform better than the ubiquitous random hyperplane technique. By establishing the usefulness of higher-dimensional rounding schemes, this fact has consequences in approximation algorithms. Specifically, it yields the best known polynomial-time approximation algorithm for the Frieze-Kannan Cut Norm problem, a generic and well-studied optimization problem with many applications.

Original languageEnglish (US)
Article numbere4
JournalForum of Mathematics, Pi
Volume1
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Algebra and Number Theory
  • Statistics and Probability
  • Mathematical Physics
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'The grothendieck constant is strictly smaller than krivine's bound'. Together they form a unique fingerprint.

Cite this