corollaryroutineinferred_dep
Gap hardness from a fixed SDP integrality gap
So an SDP integrality gap gives NP-hardness of vs
payoff of the main theorem
Corollary·
cor:raghavendra-consequence·§8.1 Constraint satisfaction and Vertex CoverStatement (paper)
Let be a fixed -instance with
.
For every fixed , it is NP-hard to distinguish
-instances satisfying
In plain English
If a fixed -instance has , then for any fixed it is NP-hard to distinguish -instances with from those with .
Why it's here
This turns a single integrality-gap example into an NP-hardness result for the whole constraint satisfaction problem, using Raghavendra's fixed-instance theorem on Unique Games instances from the strong-left lemma, which in turn comes from the Unique Games Theorem. The proof pads predicates to a common arity, runs the verifier reduction, and rounds its local law to rationals. This keeps the output an explicit polynomial-time -instance while the total loss stays within .
Classified routine:
Direct consequence of Raghavendra's theorem (Raghavendra 2008) that an SDP integrality gap yields UG-hardness, here combined with the paper's proved Unique Games Theorem via the strong-left lemma. The padding and rounding steps are standard bookkeeping.