COMPUTER SCIENCE/DISCRETE MATH, II | |

Topic: | Approximation Algorithms for Unique Games |

Speaker: | Luca Trevisan |

Affiliation: | University of California, Berkeley |

Date: | Tuesday, May 31 |

Time/Room: | 11:30am - 12:30pm/S-101 |

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.