claimroutineinferred_dep

Common Gaussian ensemble matching local moments

Gram data gives one Gaussian ensemble matching local first and second moments
setup for the invariance principle
Claim·§A.2 The finite ordering transfer·inside lemLow-influence functions cannot beat opt_q(J)

Statement (paper)

For every constraint, the common Gram data yield one Gaussian ensemble (Gu,j)(G_{u,j}), namely Gu,j=⟨I,bu,j⟩+⟨bu,j−⟨I,bu,j⟩I,g⟩G_{u,j}=\langle I,b_{u,j}\rangle+\langle b_{u,j}-\langle I,b_{u,j}\rangle I,g\rangle with gg a standard Gaussian vector in the span of the Gram vectors, for all variables of JJ, having the same first and second moments as the integral ensemble of indicators 1{Xi=j}\mathbf1_{\{X_i=j\}} under μc\mu_c on every constraint. Independent copies of this ensemble in the RR coordinates allow each HjH^j to be evaluated on both the integral and the Gaussian ensembles through the same polynomial (its multilinear product expansion), where the atoms of the integral ensemble have probability greater than α\alpha.

In plain English

For each constraint, the Gram data from the local instance gives a single Gaussian ensemble (Gu,j)(G_{u,j}) over the variables of JJ whose first and second moments equal those of the indicators 1{Xi=j}\mathbf1_{\{X_i=j\}} under μc\mu_c. Taking independent copies across the RR coordinates lets each HjH^j be evaluated on both the integral and Gaussian ensembles via the same multilinear polynomial, where every atom of the integral ensemble has probability above α\alpha.

Why it's here

This is the setup for the invariance principle in the rounding lemma. The Gram vectors from the local data are turned into a Gaussian ensemble with matching moments, and the lower bound α\alpha on atoms makes the integral side suitable for invariance. The later Lipschitz-payoff step can then compare the integral and Gaussian evaluations of the same polynomial with an error independent of RR.
Classified routine:
Standard Gaussian-ensemble construction from Gram vectors matching first and second moments, the setup used for the invariance principle of Mossel–O'Donnell–Oleszkiewicz (2010) in Raghavendra-style SDP rounding (Raghavendra 2008). It follows directly from the Gram data of lem-ordering-local-data.

Uses

lemFinite local ordering instance with Gram data

Used by

claimLipschitz payoff gives R-independent invariance error

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Common Gaussian ensemble matching local moments" rests on lem:ordering-local-data