Krivine schemes are optimal
HTML articles powered by AMS MathViewer
- by Assaf Naor and Oded Regev PDF
- Proc. Amer. Math. Soc. 142 (2014), 4315-4320 Request permission
Abstract:
It is shown that for every $k\in \mathbb {N}$ there exists a Borel probability measure $\mu$ on $\{-1,1\}^{\mathbb {R}^{k}}\times \{-1,1\}^{\mathbb {R}^{k}}$ such that for every $m,n\in \mathbb {N}$ and $x_1,\ldots , x_m,y_1,\ldots ,y_n\in \mathbb {S}^{m+n-1}$ there exist $x_1’,\ldots ,x_m’,y_1’,\ldots ,y_n’\in \mathbb {S}^{m+n-1}$ such that if $G:\mathbb {R}^{m+n}\to \mathbb {R}^k$ is a random $k\times (m+n)$ matrix whose entries are i.i.d. standard Gaussian random variables, then for all $(i,j)\in \{1,\ldots ,m\}\times \{1,\ldots ,n\}$ we have \begin{equation*} \mathbb {E}_G\left [\int _{\{-1,1\}^{\mathbb {R}^{k}}\times \{-1,1\}^{\mathbb {R}^{k}}}f(Gx_i’)g(Gy_j’)d\mu (f,g)\right ]=\frac {\langle x_i,y_j\rangle }{(1+C/k)K_G}, \end{equation*} where $K_G$ is the real Grothendieck constant and $C\in (0,\infty )$ is a universal constant. This establishes that Krivine’s rounding method yields an arbitrarily good approximation of $K_G$.References
- R. Blei, The Grothendieck inequality revisited, preprint available at http://arxiv.org/abs/1111.7304, 2012.
- Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor, The Grothendieck constant is strictly smaller than Krivine’s bound, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 453–462. MR 2932721, DOI 10.1109/FOCS.2011.77
- J. Briët, F. M. de Oliveira Filho, and F. Vallentin, Grothendieck inequalities for semidefinite programs with rank constraint, Preprint available at http://arxiv.org/pdf/1011.1754v2.pdf, 2010.
- A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques, Bol. Soc. Mat. São Paulo 8 (1953), 1–79 (French). MR 94682
- Uffe Haagerup, A new upper bound for the complex Grothendieck constant, Israel J. Math. 60 (1987), no. 2, 199–224. MR 931877, DOI 10.1007/BF02790792
- Jean-Louis Krivine, Sur la constante de Grothendieck, C. R. Acad. Sci. Paris Sér. A-B 284 (1977), no. 8, A445–A446. MR 428414
- J. Lindenstrauss and A. Pełczyński, Absolutely summing operators in $L_{p}$-spaces and their applications, Studia Math. 29 (1968), 275–326. MR 231188, DOI 10.4064/sm-29-3-275-326
- Gilles Pisier, Grothendieck’s theorem, past and present, Bull. Amer. Math. Soc. (N.S.) 49 (2012), no. 2, 237–323. MR 2888168, DOI 10.1090/S0273-0979-2011-01348-9
- J. A. Reeds, A new lower bound on the real Grothendieck constant, unpublished manuscript, available at http://www.dtc.umn.edu/reedsj/bound2.dvi, 1991.
Additional Information
- Assaf Naor
- Affiliation: Courant Institute, New York University, New York, New York 10012
- Email: naor@cims.nyu.edu
- Oded Regev
- Affiliation: École Normale Supérieure, Département d’Informatique, 45 rue d’Ulm, Paris, France
- MR Author ID: 146145
- ORCID: 0000-0002-8616-3163
- Email: regev@di.ens.fr
- Received by editor(s): May 31, 2012
- Received by editor(s) in revised form: November 15, 2012, and February 4, 2013
- Published electronically: August 18, 2014
- Additional Notes: The first author was supported by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation
The second author was supported by a European Research Council (ERC) Starting Grant - Communicated by: Thomas Schlumprecht
- © Copyright 2014 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 142 (2014), 4315-4320
- MSC (2010): Primary 46B07
- DOI: https://doi.org/10.1090/S0002-9939-2014-12169-1
- MathSciNet review: 3266999