CAM colloquium - Friday, April 7
3:30 p.m.
655 Rhodes Hall

Speaker: Noga Alon, Tel Aviv University and Institute for Advanced Study, Princeton

Title: "Approximation algorithms and Grothendieck type inequalities"

 

Abstract: I will describe a connection between a classical inequality of Grothendieck and approximation algorithms based on semidefinite 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 several extensions of the inequality of Grothendieck, 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.

The lecture will include a description of Grothendieck's Inequality, its extensions, and their relevance to approximation algorithms. The new material is based on two recent papers with A. Naor, and with K. Makarychev, Y. Makarychev and A. Naor.

 

Refreshments at 4:30 in 657 Rhodes Hall.