corollaryroutineinferred_dep

Gap hardness from a fixed SDP integrality gap

So an SDP integrality gap A<BA<B gives NP-hardness of B−ηB-\eta vs A+ηA+\eta
payoff of the main theorem
Corollary·cor:raghavendra-consequence·§8.1 Constraint satisfaction and Vertex Cover

Statement (paper)

Let JJ be a fixed Λ\Lambda-instance with A=OPT⁡(J)<B=SDP⁡R(J)A=\operatorname{OPT}(J)<B=\operatorname{SDP}_{R}(J). For every fixed 0<η<(B−A)/20<\eta<(B-A)/2, it is NP-hard to distinguish Λ\Lambda-instances II satisfying OPT⁡(I)≥B−ηfrom those satisfyingOPT⁡(I)≤A+η. \operatorname{OPT}(I)\ge B-\eta \qquad\text{from those satisfying}\qquad \operatorname{OPT}(I)\le A+\eta.

In plain English

If a fixed Λ\Lambda-instance JJ has OPT⁡(J)=A<B=SDP⁡R(J)\operatorname{OPT}(J)=A<B=\operatorname{SDP}_R(J), then for any fixed 0<η<(B−A)/20<\eta<(B-A)/2 it is NP-hard to distinguish Λ\Lambda-instances with OPT⁡≥B−η\operatorname{OPT}\ge B-\eta from those with OPT⁡≤A+η\operatorname{OPT}\le A+\eta.

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 Λ\Lambda-instance while the total loss stays within η\eta.
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.

Uses

thmThe Unique Games TheoremlemUnique Games with constant left degree and strong satisfaction

Used by

Nothing in the paper

Inside the proof

claimPadding predicates to common arityclaimFixed-instance verifier gap from strong-left UGclaimRational approximation of local lawclaimExplicit polynomial-size occurrence listclaimRationalization changes optimum by under eta/2

Sources

PaperOpen
Section
§8.1 Constraint satisfaction and Vertex Cover
Page
—
Label
cor:raghavendra-consequence
Line
sections/07-consequences.tex:64
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    critique: The proof (sections/07-consequences.tex:92-94, 117-119) uses "the formulation above" and "the nonempty simple game supplied above". That formulation is Lemma A.1, introduced at lines 55-62. The edge exists only on child claims.