Krivine schemes are optimal

Assaf Naor, Oded Regev

Research output: Contribution to journalArticlepeer-review

Abstract

It is shown that for every k ∈ ℕ there exists a Borel probability measure μ on {−1, 1}ℝk × {−1, 1}ℝk such that for every m, n ∈ ℕ and x1,...,xm, y1,..., yn ∈ Sm+n−1 there exist x′1,..., x′m, y′1,..., y′n ∈ S m+n−1 such that if G : ℝm+n → ℝk 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 where KG is the real Grothendieck constant and C ∈ (0, ∞) is a universal constant. This establishes that Krivine’s rounding method yields an arbitrarily good approximation of KG.

Original languageEnglish (US)
Pages (from-to)4315-4320
Number of pages6
JournalProceedings of the American Mathematical Society
Volume142
Issue number12
DOIs
StatePublished - 2014

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Krivine schemes are optimal'. Together they form a unique fingerprint.

Cite this