claimroutineinferred_dep

Invariance hypotheses hold for smoothed functions

Smoothed functions meet invariance hypotheses: variance, influence kqtkqt, tail
verifies the conditions of the invariance theorem
Claim·§A.2 The finite ordering transfer·inside lemLow-influence functions cannot beat opt_q(J)

Statement (paper)

For each fixed cc, with Hj=T1−λFjH^j=T_{1-\lambda}F^j, the vector (Hj(Zi))i∈[k],j∈[q](H^j(Z_i))_{i\in[k],j\in[q]} on the product ensemble μc⊗R\mu_c^{\otimes R} has components of variance at most one, and each coordinate influence at most kqtkqt, because Inf⁡ℓμc⊗R(Hj(Zi))=Inf⁡ℓ[m]R(Hj)≤t\operatorname{Inf}^{\mu_c^{\otimes R}}_\ell(H^j(Z_i))=\operatorname{Inf}^{[m]^R}_\ell(H^j)\le t. Moreover, for every real d>0d>0, Var⁡((Hj(Zi))>d)≤(1−λ)2d\operatorname{Var}\bigl((H^j(Z_i))^{>d}\bigr)\le(1-\lambda)^{2d}, with variance computed under μc⊗R\mu_c^{\otimes R}. Hence the hypotheses of the vector-valued invariance estimate [GuruswamiEtAl2011OrderingCSP, Theorem 10.1] hold.

In plain English

For each fixed cc, the vector (Hj(Zi))i,j(H^j(Z_i))_{i,j} with Hj=T1−λFjH^j=T_{1-\lambda}F^j on the product ensemble μc⊗R\mu_c^{\otimes R} has variance at most one per component, every coordinate influence at most kqtkqt, and high-degree tail variance Var⁡((Hj(Zi))>d)≤(1−λ)2d\operatorname{Var}((H^j(Z_i))^{>d})\le(1-\lambda)^{2d} for every real d>0d>0.

Why it's here

This verifies the conditions of the vector-valued invariance theorem of Guruswami et al. for the smoothed functions from the noise-factorization step. The influence bound is inherited directly from the hypothesis on Inf⁡ℓ(T1−λFj)\operatorname{Inf}_\ell(T_{1-\lambda}F^j), and the tail bound comes from the damping of degree->d>d parts by T1−λT_{1-\lambda}. Both are independent of RR, which makes the later invariance error RR-independent.
Classified routine:
A hypothesis check for the vector-valued invariance principle of Guruswami et al. (Theorem 10.1). The influence bound is inherited from the low-influence assumption, and the tail bound is the standard decay of high-degree Fourier weight under the noise operator T1−λT_{1-\lambda}.

Uses

claimNoise factorizes into smoothed function payoff

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:576
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Influence and tail hypotheses for invariance" rests on claim-lem-ordering-rounding-1