Optimal Long Code Test with One Free Bit
Nikhil Bansal, Subhash Khot · 2009
For arbitrarily small constants epsilon, delta ¿.¿ > 0, we present a long code test with one free bit, completeness 1-epsilon and soundness delta. Using the test, we prove the following two inapproximability results:1. Assuming the Unique Games Conjecture of Khot, given an n-vertex graph that has two disjoint independent sets of size (1/2-¿)n each, it is NP-hard to find an independent set of size delta n.2. Assuming a (new) stronger version of the Unique Games Conjecture, the scheduling problem of minimizing weighted completion time with precedence constraints is inapproximable within factor 2-¿.