Krivine schemes are optimal

Assaf Naor Oded Regev 1
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Grothendieck's inequality asserts that there exists a constant K>0 such that for every m,n and every m×n matrix A=(aij) with real entries and every choice of unit vectors x1,…,xm,y1,…,yn∈Sm+n−1, there are signs ε1,…,εm,δ1,…,δn∈{−1,1} satisfying ∑mi=1∑nj=1aij⟨xi,yj⟩≤K∑mi=1∑nj=1aijεiδj. The infimum over those K for which this inequality holds is called the (real) Grothendieck constant and is denoted KG. In order to investigate the exact value of KG, the authors introduce the following definition. A Borel probability measure μ on {−1,1}Rk×{−1,1}Rk is a k-dimensional Krivine scheme of quality K>0 if for every m,n and every choice of unit vectors x1,…,xm,y1,…,yn∈Sm+n−1, there exist new unit vectors x′1,…,x′m,y′1,…,y′n∈Sm+n−1 such that if G:Rm+n→Rk is a random k×(m+n) matrix whose entries are i.i.d. standard Gaussian random variables, then for all (i,j)∈{1,…,m}×{1,…,n} we have EG[∫{−1,1}Rk×{−1,1}Rkf(Gx′i)g(Gy′j)dμ(f,g)]=1K⟨xi,yj⟩. The authors note that the existence of a k-dimensional Krivine scheme of quality K>0 implies that KG≤K. A special one-dimensional Krivine scheme was introduced by J.-L. Krivine [C. R. Acad. Sci. Paris Sér. A-B 284 (1977), no. 8, A445–A446; MR0428414 (55 #1435)] in order to obtain a new upper bound on KG. Krivine conjectured that his bound is exact. This conjecture was refuted [M. Braverman et al., in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, 453–462, IEEE Computer Soc., Los Alamitos, CA, 2011; MR2932721] yielding a better upper bound on KG via a two-dimensional Krivine scheme. In the paper under review the authors prove the optimality of the Krivine scheme: For every k∈N there exists a k-dimensional Krivine scheme of quality (1+O(1/k))KG.
Type de document :
Article dans une revue
Proceedings of the American Mathematical Society, American Mathematical Society, 2012, 142 (12), pp.4315-4320
Liste complète des métadonnées

https://hal.inria.fr/hal-01111613
Contributeur : Brigitte Briot <>
Soumis le : vendredi 30 janvier 2015 - 16:24:19
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10

Identifiants

  • HAL Id : hal-01111613, version 1

Collections

Citation

Assaf Naor, Oded Regev. Krivine schemes are optimal. Proceedings of the American Mathematical Society, American Mathematical Society, 2012, 142 (12), pp.4315-4320. 〈hal-01111613〉

Partager

Métriques

Consultations de la notice

68