[talks] K Makarychev preFPO

[Melissa M Lawson]

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.