DIMACS Theoretical Computer Science Seminar

Title: Quadratic forms on graphs

Speaker: Konstantin Makarychev, Princeton University

Date: March 22, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, CoRE 229***, Rutgers University, Busch Campus, Piscataway, NJ

**Please note room change for this week only


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.