# CSAIL Event Calendar: Previous Series

 The Grothendieck constant is strictly smaller than KrivineSpeaker: Yury Makarychev , TTI, U ChicagoDate: November 8 2011 Time: 4:15PM to 5:15PM Location: 32-124Host: Costis Daskalakis, CSAIL, MITContact: Be Blackburn, 3-6098, be@csail.mit.eduRelevant URL: I will talk about Grothendieck's Inequality. The inequality was proved by Grothendieck in 1953, and since then it has found numerous applications in Analysis, Quantum Mechanics and Computer Science. From the point of view of combinatorial optimization, the inequality states that the integrality gap of a certain semi-definite program is less than some absolute constant. The optimal value of this constant is called the Grothendieck constant K_G. The Grothendieck constant lies between 1.67 and 1.79, however, its exact value is unknown. The last progress on this problem was in 1977, when Krivine proved that K_G \leq \pi / (2 log(1+\sqrt{2})) and conjectured that his bound is optimal. In this talk, we will disprove this conjecture and show that K_G is strictly less than Krivine's bound. We will show that for this problem a new binary rounding scheme, which projects vectors on a random 2 dimensional subspace, performs better than the ubiquitous random hyperplane technique. Joint work with Mark Braverman (University of Toronto), Konstantin Makarychev (IBM Research), Assaf Naor (Courant Institute).See other events that are part of Theory Colloquium 2011/2012See other events happening in November 2011