The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

We prove that for an arbitrarily small constant \eps>0, assuming NP\not \subseteqDTIME(2^{{\log^{O(1/\epsilon)} n}}), the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than 2^{\log ^{1-\epsilon}n}. This improves upon the previous hardness factor of (\log n)^\delta for some $\delta ... more >>>

Håstad established that any predicate P \subseteq \{0,1\}^m containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang ... more >>>