TY - GEN
T1 - Optimal long code test with one free bit
AU - Bansal, Nikhil
AU - Khot, Subhash
PY - 2009
Y1 - 2009
N2 - 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 - ε.
AB - 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 - ε.
UR - http://www.scopus.com/inward/record.url?scp=77952368191&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952368191&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2009.23
DO - 10.1109/FOCS.2009.23
M3 - Conference contribution
AN - SCOPUS:77952368191
SN - 9780769538501
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 453
EP - 462
BT - Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
T2 - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Y2 - 25 October 2009 through 27 October 2009
ER -