claimroutineinferred_dep

Gaussian side is a random q-assignment

Gaussian side is a random qq-assignment, so payoff ≤ opt⁡q(J)\operatorname{opt}_q(J)
Gaussian-side upper bound
Claim·§A.2 The finite ordering transfer·inside lemLow-influence functions cannot beat opt_q(J)

Statement (paper)

On the common Gaussian ensemble, projecting H(Gu)H(G_u) to Sq\mathcal S_q for every u∈Uu\in U and independently drawing one qq-label for each uu with those probabilities gives a random assignment of JJ, whose conditional expected payoff at each local tuple is the multilinear payoff Ψ\Psi, since the variables in every local tuple are distinct. Consequently the Gaussian expected payoff is at most opt⁡q(J)\operatorname{opt}_q(J), because every realized assignment has value at most opt⁡q(J)\operatorname{opt}_q(J).

In plain English

On the common Gaussian ensemble, projecting H(Gu)H(G_u) onto Sq\mathcal S_q for each variable u∈Uu\in U and drawing an independent qq-label per uu from those probabilities yields a random assignment of JJ. Its expected payoff at each local tuple equals the multilinear payoff Ψ\Psi, so the Gaussian expected payoff is at most opt⁡q(J)\operatorname{opt}_q(J).

Why it's here

This gives the Gaussian-side upper bound in the parent lemma's proof. Because the variables in each local tuple are distinct, the independent label draws make the conditional expected payoff exactly the multilinear Ψ\Psi, and since every realized assignment is worth at most opt⁡q(J)\operatorname{opt}_q(J), so is the average. Combined with the RR-independent invariance error rs(kqt)r_s(kqt) from the preceding claim, this yields the bound opt⁡q(J)+rs(kqt)\operatorname{opt}_q(J)+r_s(kqt).
Classified routine:
Standard Raghavendra-style rounding step: independent randomized rounding of distributions makes the expected payoff equal the multilinear extension on tuples of distinct variables, so by averaging it is at most the optimum (Raghavendra 2008).

Uses

claimLipschitz payoff gives R-independent invariance error

Used by

Nothing in the paper

Sources

PaperOpen
Section
§A.2 The finite ordering transfer
Page
—
Label
—
Line
appendices/finite-consequences.tex:642
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Gaussian side is a random q-assignment" rests on claim-lem-ordering-rounding-4