# The Grothendieck Constant is Strictly Smaller than Krivine's Bound

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

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1jv7m`

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.