Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Krivine schemes are optimal

Authors: Assaf Naor and Oded Regev
Journal: Proc. Amer. Math. Soc. 142 (2014), 4315-4320
MSC (2010): Primary 46B07
Published electronically: August 18, 2014
MathSciNet review: 3266999
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle \mathbb{E}_G\left [\int _{\{-1,1\}^{\mathbb{R}^{k}}\times \{-1,1\... ...f(Gx_i')g(Gy_j')d\mu (f,g)\right ]=\frac {\langle x_i,y_j\rangle }{(1+C/k)K_G},$    

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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 46B07

Retrieve articles in all journals with MSC (2010): 46B07

Additional Information

Assaf Naor
Affiliation: Courant Institute, New York University, New York, New York 10012

Oded Regev
Affiliation: École Normale Supérieure, Département d’Informatique, 45 rue d’Ulm, Paris, France

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
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society