Konstantin Makarychev will present his preFPO on Tuesday, May 1 at 11am in room 302 (note room). The members his committee are: Moses Charikar (advisor), Boaz Barak and Assaf Naor (NYU) (readers), Bernard Chazelle and Robert Tarjan (non-readers). Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------------------------- Title: Quadratic Forms on Graphs and Their Applications Abstract: We introduce a new graph parameter, called the Grothendieck constant of a graph, which is defined as the (worst case) integrality gap of the semidefinite relaxation for the problem of maximizing of a certain quadratic form (which depends on the graph). This problem arises in several applications including the study of correlation clustering and the investigation of the spin glass model. We give upper and lower estimates for the Grothendieck constant of a graph G: We show that it is less than O(log T(G)), where T(G) is the Lovasz Theta Function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G. We also prove that the Grothendieck constant is always at least c.log w(G), where w(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices is c.log n. The lower bound for the complete graph also improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions. I will also show how similar methods can be used for finding approximate solutions of constraint satisfaction and graph arrangements problems.