claimroutineinferred_dep
Rationalization changes optimum by under eta/2
Rationalizing shifts values by , giving gap vs
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 , , where the original and rationalized instances use the same variable set. Consequently the optima of the two instances differ by at most , so the imported gap yields optimum at least in the YES case and at most in the NO case.
In plain English
Replacing the local law by its rational approximation changes the value of every assignment by at most on the same variable set, so the optima differ by at most . Hence the verifier gap becomes optimum at least (YES) and at most (NO).
Why it's here
The two instances share variables and differ only in the local law, and total variation distance bounds the change in expected value of any assignment, which is what gives the bound. Combined with the verifier gap ( vs ), the extra loss under for the explicit rational instance gives the stated versus 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.