Skip to main content

The Grothendieck Constant is Strictly Smaller than Krivine's Bound

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1jv7m
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorMakarychev, Konstantin-
dc.contributor.authorMakarychev, Yury-
dc.contributor.authorNaor, Assaf-
dc.date.accessioned2021-10-08T19:44:49Z-
dc.date.available2021-10-08T19:44:49Z-
dc.date.issued2013en_US
dc.identifier.citationBraverman, 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.4en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1jv7m-
dc.description.abstractThe (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.en_US
dc.format.extente4en_US
dc.language.isoen_USen_US
dc.relation.ispartofForum of Mathematicsen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleThe Grothendieck Constant is Strictly Smaller than Krivine's Bounden_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1017/fmp.2013.4-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
GrothendieckConstanttSmallerKrivineBoundcambridge.pdf1.03 MBAdobe PDFView/Download


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