Originally, Grothendieck's inequality arose in the study of norms on tensor products of Banach spaces. In recent years Grothendieck-type inequalities have found many applications in mathematics and computer science, including approximation algorithms, extremal combinatorics, communication complexity, machine learning, and quantum information theory. Grothendieck-type inequalities can be seen as the integrality gap between a quadratic optimization problem with rank constraint (difficult) and its natural semidefinite programming relaxation (easy). For instance, the SDP approximation algorithm for MAXCUT of Goemans and Williamson fits into this framework.
The unique games conjecture states roughly that, unless P = NP, there is no polynomial-time approximation algorithm achieving a sensible approximation ratio for the unique games problem (which is a specific combinatorial optimization problem). The UGC implies that there is no polynomial-time approximation algorithm which improves on the natural SDP relaxations in Grothendieck-type inequalities. For instance, the MAXCUT algorithm of Goemans and Williamson is optimal in this sense.
In the tutorial I want to give several examples of Grothendieck-type inequalities together with applications. Then I plan to give an introduction to the unique games conjecture and its relation to Grothendieck-type inequalities.
Copyright. All Rights Reserved.