claimroutineinferred_dep

Rationalization changes optimum by under eta/2

Rationalizing shifts values by <η/2<\eta/2, giving gap B−ηB-\eta vs A+ηA+\eta
finishes the corollary's gap
Claim·§8.1 Constraint satisfaction and Vertex Cover·inside corGap hardness from a fixed SDP integrality gap

Statement (paper)

For every assignment σ\sigma, ∣val⁡θ^(σ)−val⁡θ(σ)∣≤δ<η/2\bigl|\operatorname{val}_{\widehat\theta}(\sigma)-\operatorname{val}_{\theta}(\sigma)\bigr|\le\delta<\eta/2, where the original and rationalized instances use the same variable set. Consequently the optima of the two instances differ by at most δ<η/2\delta<\eta/2, so the imported gap yields optimum at least B−ηB-\eta in the YES case and at most A+ηA+\eta in the NO case.

In plain English

Replacing the local law θ\theta by its rational approximation θ^\widehat\theta changes the value of every assignment σ\sigma by at most δ<η/2\delta<\eta/2 on the same variable set, so the optima differ by at most δ\delta. Hence the verifier gap becomes optimum at least B−ηB-\eta (YES) and at most A+ηA+\eta (NO).

Why it's here

The two instances share variables and differ only in the local law, and total variation distance δ\delta bounds the change in expected value of any assignment, which is what gives the δ\delta bound. Combined with the verifier gap (>B−η/2>B-\eta/2 vs ≤A+η/2\le A+\eta/2), the extra loss under η/2\eta/2 for the explicit rational instance gives the stated B−ηB-\eta versus A+ηA+\eta gap, completing the corollary.
Classified routine:
A direct consequence of the earlier rational-approximation step: a total variation bound of delta on the local law bounds the change in every assignment's value, and hence the optimum, by delta. Combining this with the eta/2 verifier gap is simple bookkeeping.

Uses

claimFixed-instance verifier gap from strong-left UGclaimRational approximation of local lawclaimExplicit polynomial-size occurrence list

Used by

Nothing in the paper

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Rationalization changes optimum by under eta/2" rests on claim-cor-raghavendra-consequence-2
  • info
    inferred_dep
    outline: "Rationalization changes optimum by under eta/2" rests on claim-cor-raghavendra-consequence-3
  • info
    inferred_dep
    outline: "Rationalization changes optimum by under eta/2" rests on claim-cor-raghavendra-consequence-4