Optimal Long Code Test with One Free Bit

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-¿.

Authors

• Nikhil Bansal 0001
• Subhash Khot

Keywords

• Polynomials
• NP-complete problem
• Computer science
• Single machine scheduling
• Acoustic testing
• Time factors
• Free Bits
• Independent Set
• Precedence Constraints
• Test Analysis
• Authoritarian
• Hardness
• Sunflower
• Functional Sequences
• Minimum Coverage
• Probability 1
• Unified Representation
• Sound Properties
• Identically Zero
• Boolean Function
• Hypotheses Of Theorem
• Vertex Cover
• Unique Games
• 1 Free bit
• Precedence constrained scheduling