corollaryroutineinferred_dep

Gap hardness from a fixed SDP integrality gap

So an SDP integrality gap

A<B

gives NP-hardness of

B-\eta

A+\eta

payoff of the main theorem

Corollary·cor:raghavendra-consequence·§8.1 Constraint satisfaction and Vertex Cover

Statement (paper)

Let

J

be a fixed

\Lambda

-instance with

A=\operatorname{OPT}(J)<B=\operatorname{SDP}_{R}(J)

. For every fixed

0<\eta<(B-A)/2

, it is NP-hard to distinguish

\Lambda

-instances

I

satisfying

\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

J

has

\operatorname{OPT}(J)=A<B=\operatorname{SDP}_R(J)

, then for any fixed

0<\eta<(B-A)/2

it is NP-hard to distinguish

\Lambda

-instances with

\operatorname{OPT}\ge B-\eta

from those with

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

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

Selected node

Statement (paper)

In plain English

Why it's here

Inside the proof