Skip to main content

The Grothendieck Constant is Strictly Smaller than Krivine's Bound

Author(s): Braverman, Mark; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf

To refer to this page use:
Abstract: The (real) Grothendieck constant 𝐾𝐺 is the infimum over those 𝐾∈(0,∞) such that for every π‘š,π‘›βˆˆβ„• and every π‘šΓ—π‘› real matrix (π‘Žπ‘–π‘—) we have max{π‘₯𝑖}π‘šπ‘–=1,{𝑦𝑗}𝑛𝑗=1βŠ†π‘†π‘›+π‘šβˆ’1βˆ‘π‘–=1π‘šβˆ‘π‘—=1π‘›π‘Žπ‘–π‘—βŸ¨π‘₯𝑖,π‘¦π‘—βŸ©β©½πΎmax{πœ€π‘–}π‘šπ‘–=1,{𝛿𝑗}𝑛𝑗=1βŠ†{βˆ’1,1}βˆ‘π‘–=1π‘šβˆ‘π‘—=1π‘›π‘Žπ‘–π‘—πœ€π‘–π›Ώπ‘—. The classical Grothendieck inequality asserts the nonobvious fact that the above inequality does hold true for some 𝐾∈(0,∞) that is independent of π‘š,𝑛 and (π‘Žπ‘–π‘—) . 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 𝐾𝐺 remains a mystery. The last progress on this problem was in 1977, when Krivine proved that πΎπΊβ©½πœ‹/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 (π‘Žπ‘–π‘—) which exhibit (asymptotically, as π‘š,π‘›β†’βˆž ) a lower bound on 𝐾𝐺 that matches Krivine’s bound. Here, we obtain an improved Grothendieck inequality that holds for all matrices (π‘Žπ‘–π‘—) and yields a bound 𝐾𝐺<πœ‹/2log(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 ℝ2 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.
Publication Date: 2013
Citation: Braverman, Mark, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. "The Grothendieck Constant is Strictly Smaller than Krivine's Bound." Forum of Mathematics, Pi 1 (2013): e4. doi:10.1017/fmp.2013.4
DOI: 10.1017/fmp.2013.4
Pages: e4
Type of Material: Journal Article
Journal/Proceeding Title: Forum of Mathematics
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.