Graph Partitioning, Clustering with Qualitative Information, and<br/><br/>Grothendieck-type Inequalities

Friday, September 30, 2005 - 1:25pm - 2:25pm
Assaf Naor (Microsoft Research)
In this talk we will describe applications of Grothendieck's
inequality to combinatorial optimization. We will show how Grothendieck's
inequality can be used to provide efficient algorithms which approximate
the cut-norm of a matrix, and construct Szemeredi partitions. Moreover, we
will show how to derive a new class of Grothendieck type inequalities
which can be used to give approximation algorithms for Correlation
Clustering on a wide class of judgment graphs, and to approximate ground
states of spin glasses. No prerequisites will be assumed, in particular,
we will present a proof of Grothendieck's inequality.

Based on joint works with N. Alon, K. Makarychev and Y. Makarychev.