10 Lectures and 42 Open Problems — The Grothendieck Constant
For positive integers and a real matrix , define the sign optimum and vector optimum by
where is the unit sphere in . The real Grothendieck constant is
The question is to determine the exact value of . Braverman, Makarychev, Makarychev, and Naor (2013) New Lower and Upper Bounds for the Grothendieck Constant
Background
Grothendieck’s inequality asserts that the ratio between the vector optimum and the sign optimum is bounded by a universal constant, uniformly over all matrix dimensions and coefficients. In optimization, this constant is the worst-case integrality gap of the canonical semidefinite relaxation of a bilinear sign problem; the inequality also has important roles in the geometry of Banach spaces, operator spaces, harmonic analysis, and quantum information. New Lower and Upper Bounds for the Grothendieck Constant
Since Grothendieck’s 1953 discovery, the central challenge has been to narrow the gap between constructions giving lower bounds and rounding schemes giving upper bounds. Krivine’s 1977 scheme first lifts the vectors to an infinite-dimensional space and then rounds them by a random hyperplane, yielding . Krivine conjectured that this was exact. Braverman, Makarychev, Makarychev, and Naor disproved the conjecture by mixing hyperplane rounding with a non-hyperplane method; their argument uses random two-dimensional projections and a suitable partition of the plane. The Grothendieck Constant is Less Than {π/2 log(1+√2)}-10^{-5} Braverman, Makarychev, Makarychev, and Naor (2013)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.