lemmaroutineinferred_depunresolved_ref

Low-influence functions cannot beat opt_q(J)

Low-influence rounding gets payoff ≤ opt⁡q(J)+rs\operatorname{opt}_q(J)+r_s, independent of RR
soundness bound for pseudorandom vertices
Lemma·lem:ordering-rounding·§A.2 The finite ordering transfer

Statement (paper)

Let J,μc,αJ,\mu_c,\alpha be the data of Lemma , and fix 0<λ<10<\lambda<1. For an integer R≥1R\ge1, choose cc with probability ωc\omega_c. Conditional on this one choice of cc, choose the RR coordinate tuples independently from μc\mu_c, producing strings Z1,…,Zk∈[m]RZ_1,\ldots,Z_k\in[m]^R. Then obtain Z~i\widetilde Z_i by independently resampling every position and coordinate uniformly with probability λ\lambda. For a single function F=(F1,…,Fq):[m]R→SqF=(F^1,\ldots,F^q):[m]^R\to\mathcal S_q, used for every cc and every position, suppose that 0<t<1/(kq)0<t<1/(kq) and Inf⁡ℓ(T1−λFj)≤t(ℓ∈[R], j∈[q]). \operatorname{Inf}_\ell(T_{1-\lambda}F^j)\le t \quad(\ell\in[R],\ j\in[q]). Then Ec,Z,Z~P0ml(F(Z~1),…,F(Z~k))≤opt⁡q(J)+rs(kqt), \mathbb E_{c,Z,\widetilde Z} P_0^{\mathrm{ml}}\bigl(F(\widetilde Z_1),\ldots, F(\widetilde Z_k)\bigr) \le \operatorname{opt}_q(J)+r_s(kqt), where rs(u)→0r_s(u)\to0 as u↓0u\downarrow0, independently of RR. The function rsr_s depends only on the fixed local data, k,q,λk,q,\lambda.

In plain English

Take the local instance JJ with laws μc\mu_c and atom bound α\alpha, and a noise rate 0<λ<10<\lambda<1. If F:[m]R→SqF:[m]^R\to\mathcal S_q has Inf⁡ℓ(T1−λFj)≤t<1/(kq)\operatorname{Inf}_\ell(T_{1-\lambda}F^j)\le t<1/(kq) for all ℓ,j\ell,j, then its expected payoff P0mlP_0^{\mathrm{ml}} on noise-perturbed local tuples is at most opt⁡q(J)+rs(kqt)\operatorname{opt}_q(J)+r_s(kqt), where rs(u)→0r_s(u)\to0 as u↓0u\downarrow0 and rsr_s does not depend on RR.

Why it's here

This is the soundness step for the finite ordering transfer: a low-influence rounding of RR coordinates does no better on the local instance than the best qq-valued assignment of JJ, up to an RR-independent error. The proof smooths FF to H=T1−λFH=T_{1-\lambda}F, uses the invariance principle with the Gram-data Gaussian ensemble to pass to Gaussian inputs, and then reads the Gaussian side as a random qq-assignment of JJ, which is bounded by opt⁡q(J)\operatorname{opt}_q(J).
Classified routine:
Standard Raghavendra-style soundness step: smooth to T_{1-λ}F, apply the Mossel–O'Donnell–Oleszkiewicz / Mossel invariance principle to pass to correlated Gaussians matching the local Gram data, then read the Gaussian side as a random q-assignment bounded by opt_q(J). The argument is adapted from Raghavendra (2008) and does not introduce a new technique.

Uses

lemFinite local ordering instance with Gram data

Used by

propFinite ordering transfer from Unique GamesclaimCoarse completeness in independent neighbor experimentclaimPseudorandom vertices have local payoff boundclaimParameter choices give final ordering gap

Inside the proof

claimNoise factorizes into smoothed function payoffclaimCommon Gaussian ensemble matching local momentsclaimInvariance hypotheses hold for smoothed functionsclaimLipschitz payoff gives R-independent invariance errorclaimGaussian side is a random q-assignment

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    The proof uses the Gram data and the atom bound α, which are supplied by Lemma A.3 ("the data of Lemma "); that reference sits in the statement, not as a linked \ref.
  • warn
    unresolved_ref
    Key step is the external vector-valued invariance theorem (Guruswami et al. Thm 10.1 / Isaksson–Mossel).