claimroutineinferred_dep

Rational approximation of local law

Local law rounds to a rational table within total variation <η/2<\eta/2
makes the output instance rational
Claim·§8.1 Constraint satisfaction and Vertex Cover·inside corGap hardness from a fixed SDP integrality gap

Statement (paper)

For the fixed invocation (fixed JJ, η\eta, and alphabet [M][M]), the local probability law θ\theta on the finite set S\mathcal S depends only on J,η,MJ,\eta,M, and there is a rational probability vector θ^∈Q≥0S\widehat\theta\in\mathbb Q_{\ge0}^{\mathcal S} with ∑s∈Sθ^(s)=1\sum_{s\in\mathcal S}\widehat\theta(s)=1 and δ:=12∑s∈S∣θ^(s)−θ(s)∣<η/2\delta:=\frac12\sum_{s\in\mathcal S}|\widehat\theta(s)-\theta(s)|<\eta/2; this rational table is fixed finite data of the reduction.

In plain English

For the fixed invocation, the local probability law θ\theta on the finite set S\mathcal S depends only on J,η,MJ,\eta,M, and it can be replaced by a rational probability vector θ^\widehat\theta whose total variation distance δ\delta from θ\theta is less than η/2\eta/2.

Why it's here

The verifier from the previous claim may use irrational probabilities, which cannot be written down in a polynomial-time reduction. Since θ\theta lives on a finite set determined only by the fixed data, one can round it to a rational table of constant size, which is hardcoded into the reduction. The bound δ<η/2\delta<\eta/2 is what the later claims use to show that rationalizing changes every assignment's value by less than η/2\eta/2, keeping the total loss within η\eta.
Classified routine:
Density of the rationals: a probability vector on a fixed finite set can be rounded to a rational probability vector within any positive total variation distance. Here this bookkeeping is applied to the local law from the preceding fixed-instance verifier claim.

Uses

claimFixed-instance verifier gap from strong-left UG

Used by

claimExplicit polynomial-size occurrence listclaimRationalization changes optimum by under eta/2

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Rational approximation of local law" rests on claim-cor-raghavendra-consequence-2