Here is an account of Subhash Khot’s Cambridge talk. It surveys many subjects to be covered in Paris next week, so it may serve as a guide for the workshop.
In Claire Mathieu’s lecture nr 1, combinatorial optimisation problems like CLIQUE, MAX 3SAT, SET COVER were introduced. Algorithms providing approximate solutions were given. For instance, the trivial algorithm (assign random values to variables) gives an approximation ratio of 7/8 for MAX 3SAT. A linear programming based algorithm gives an approximation ratio of log(n) for SET COVER.
It turns out that these ratios are nearly optimal in the following sense. For every r>7/8, the problem of computing an assignment of variables for a 3SAT instance that satisfies a fraction of constraints >r is NP-hard. In the same way, there is a constant C such that the problem of computing a set cover with value >C log(n) is NP-hard.
Both results follow indirectly from the Probabilistically Checkable Proofs (PCP) theorem. This theorem, and its proof, will be the subject of Dinur’s course next week, and techniques to deduce from it inapproximability results will be covered in O’Donnell’s course.
For most problems, there remains a gap between known algorithms and inapproximability bounds. For instance, SPARSEST CUT has a (log n)^1/2 approximation, but the known inapproximability ratio is merely 1+… MAX CUT has a 0.878… approximation, but the best known inapproximability ratio is 16/17.
Subhash Khot’s Unique Games Conjecture UGC is an attempt to fill in these gaps. It is akin to the PCP theorem, in that it states inapproximability of a class of problems with a rough ratio (an arbitrarily small constant). However, it has been shown to imply sharp inapproximability ratios. For instance, it implies inapproximability of MAX CUT beyond the ratio 0.878… provided by the Goemans-Williamson algorithm (in his course in the second week of march, Prasad Raghavendra will explain this and a generalisation to a vast class of constraint satisfaction problems).
A definition of unique games can be found in Claire Mathieu’s lecture nr 4. A unique game is a constraint satisfaction problem of a very special type. Variables are not boolean but take values in a finite set F with k elements. Constraints are binary, i.e. each of them involves exactly two variables. Uniqueness means that each constraint is given by a permutation of F, i.e. for each value of the first variable, the constraint is satified by a unique value of the second one.
It is trivial to decide wether a given unique game has a full solution, i.e. an assignment satisfying all constraints. The conjecture focusses on instances which are nearly fully satisfiable, i.e. where a fraction 1-eps of constraints can be satisfied. There is an algorithm, due to Luca Trevisan (see Claire Mathieu’s lecture nr 4), which finds an assignment satisfying a fraction 1-eps’ of constraints, but with eps’ which degrades with n. The conjecture asks for an eps’ independant on n, and arbitrarily close to 1 when |F| tends to infinity.
In his survey, Khot gave an intuitive explanation of the connection of UGC with expansion of small sets in graphs. The Small Set Expansion Conjecture (SSE) states that for all eps>0, there exists r such that it is NP-hard to decide, given a graph G, whether
– for every subset of size r|G|, edge expansion (i.e. size of vertex bounday, in Alain Valette‘s terminology) is >1/2,
– or there exists a subset of size r|G| whose edge expansion is < eps.
The SSE conjecture implies UGC. Indeed, a unique game can be coded by a graph structure on VxF where V denotes the set of variables. And an assignment satisfying nearly all constraints produces a subset of small expansion, of relative size 1/|F|. This geometric point of view also allowed Sanjeev Arora, Boaz Barak and David Steurer to design a subexponential algorithm for unique games. We shall learn more from Steurer’s talks next week.
Khot formulated 3 open problems, but it went too fast for me to reproduce (and understand) them.
– A problem related to the SSE conjecture. If valid, the conjecture would imply existence of graphs with very many low (or close to 1, matter of convention) eigenvalues.
– A problem concerning integrality gaps of SDP relaxations of MAX CUT. Jean-Bernard Lasserre has introduced a hierarchy of richer and richer relaxations refining the Goemans-Williamson relaxation. It is unknown wether the integrality gap decreases (Lasserre will lecture on this in two weeks).
– A problem concerning the standard SDP relaxation of the unique games problem.