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.
