Computer Science/Discrete Mathematics Seminar II

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an epsilon fraction of constraints. Recent work has shown that the conjecture implies a number of very strong inapproximability results, including tight results for Max Cut and Vertex Cover. Generalizations of the conjecture to the case of sub-constant epsilon have also been considered, and shown to imply inapproximability results for Sparsest Cut and other problems. We show that a strong generalization of the conjecture to sub-constant epsilon fails. Namely, we show that, given a system of constraints and the promise that there is an assignment that satisfies a 1-1/O(log n)) fraction of constraints, we can find in polynomial time an assignment that satisfies 99% of the constraints. Feige and Reichman have shown that the problem of finding a solution that maximizes the number of satisfied constraints is hard to approximate within a 2^{(log n)^.99} factor, and so our work shows that the promise that the system is almost satisfiable changes its approximability a lot.