claimroutineinferred_dep
Fixed-instance verifier gap from strong-left UG
Raghavendra's theorem on UG gives verifier gap vs
turns UG hardness into a gap for
Claim·§8.1 Constraint satisfaction and Vertex Cover·inside corGap hardness from a fixed SDP integrality gap
Statement (paper)
Applying Raghavendra's fixed-instance theorem [RaghavendraThesis09, Theorem 7.9] with tolerance , whose premise is supplied by the formulation above and Theorem with a fixed alphabet determined by and , yields verifier instances whose optimum is greater than in the YES case and at most in the NO case.
In plain English
Applying Raghavendra's fixed-instance theorem with tolerance to hard Unique Games instances over a fixed alphabet (depending on and ) gives verifier instances with optimum greater than when the formula is satisfiable and at most when it is not.
Why it's here
This is the step where the hardness of Unique Games is turned into a gap for the fixed instance . Its premise is the padded, uniform-arity form of from the previous claim, and the Unique Games input comes from the theorem and the strong-left lemma. Later claims then round the verifier's local law to rationals, so the final instances stay within the stated slack.
Classified routine:
A direct application of Raghavendra's fixed-instance theorem (Raghavendra's thesis 2009, Theorem 7.9) with tolerance η/2. Its Unique Games premise is supplied by the paper's UG theorem and the strong-left lemma, which is standard bookkeeping.