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.