Graph Partitioning, Clustering with Qualitative Information, 
and Grothendieck-type Inequalities 

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 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.