Members’ Seminar

I will describe a connection between a classical inequality of Grothendieck and approximation algorithms based on semi-definite programming. The investigation of this connection suggests the definition of a new graph parameter, called the Grothendieck constant of a graph, whose study is motivated by algorithmic applications and leads to an improvement of a recent result of Kashin and Szarek, and to a solution of a problem of Megretski and of Charikar and Wirth. Most of the lecture will be based on recent joint work with A. Naor, and with K. Makarychev, Y. Makarychev and A. Naor.