Optimal long code test with one free bit

Abstract

For arbitrarily small constants ε, δ > 0, we present a long code test with one free bit, completeness 1 - ε and soundness δ. Using the test, we prove the following two inapproximability results: 1) Assuming the Unique Games Conjecture of Khot [15], 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 δn. 2) Assuming a (new) stronger version of the Unique Games Conjecture, the scheduling problem of minimizing weighted completion time with precedence constraints is inapprox-imable within factor 2 - ε. © 2009 IEEE.