Title: Quadratic forms on graphs

Speaker: Konstantin Makarychev, Princeton Univ.

			Abstract

We introduce a new graph parameter, called the Grothendieck constant 
of a graph. This parameter is a generalization of the classical 
Grothendieck constant; and it is equal to an integrality gap of a 
certain SDP problem, which has various algorithmic applications. Our 
results improve a recent result of Kashin and Szarek on Gram matrices of 
uniformly bounded functions, and settle a problem of Megretski and of 
Charikar and Wirth.

Joint work with Noga Alon, Yury Makarychev, Assaf Naor.

-------------------------------------------------------------------