The Unique Games Conjecture and some of its Implications on Inapproximability

In this report, we study the Unique Games conjecture of Khot [32] and its implications on the hardness of approximating some important optimization problems. The conjecture states that it is NP-hard to determine whether the value of a unique 1-round game between two provers and a verifier is close to 1 or negligible. It gives rise to PCP systems where the verifier needs to query only 2 bits from the provers (in contrast, Håstad’s verifier queries 3 bits [44]). We start by investigating the conjecture through the lens of Håstad’s 3-bit PCP. We then discuss in detail two results that are consequences of the conjecture. The first states that Min-2SAT-Deletion is NP-hard to approximate within any constant factor [32]. The second result shows that minimum vertex cover is NP-hard to approximate within a factor of 2 − ɛ for every ɛ> 0 [34]. We display the use of Fourier techniques for analyzing the soundness of the PCP used to prove the first result, and we display the use of techniques from extremal combinatorics for analyzing the soundness of the PCP used to prove the second result. Finally, we present Khot’s algorithm which shows that for the conjecture to be true, the domain of answers of the two provers must be large, and we survey some recent results examining th