Skip to Main content Skip to Navigation
Journal articles

Krivine schemes are optimal

Assaf Naor 1 Oded Regev 2 
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique - ENS Paris, 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Brigitte Briot Connect in order to contact the contributor
Submitted on : Friday, January 30, 2015 - 4:24:19 PM
Last modification on : Friday, April 29, 2022 - 1:56:08 PM


  • HAL Id : hal-01111613, version 1



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⟩



Record views