lemmaroutine

Finite local ordering instance with Gram data

Finite local instance: qq-valued opt ≤ ρΠ+η\rho_\Pi+\eta, local laws ≥ 1−η1-\eta
gadget giving completeness, soundness and Gram data
Lemma·lem:ordering-local-data·§A.2 The finite ordering transfer

Statement (paper)

For every integer q≥1q\ge1 and rational η>0\eta>0, there are a finite local instance J=(U,C,ω)J=(U,\mathcal C,\omega), with ∣U∣=m≥2|U|=m\ge2, and probability laws μc\mu_c on [m]k[m]^k with the following properties. Every tuple cc has kk distinct variables; the weights ωc\omega_c and all atoms of μc\mu_c are rational. Every one-position marginal of μc\mu_c is uniform on [m][m], and there is a fixed 0<α≤1/20<\alpha\le1/2 such that μc(x)>α\mu_c(x)>\alpha for every c,xc,x. Moreover opt⁡q(J)≤ρΠ+η,vloc:=∑cωcEX∼μcP0‾(X)≥1−η. \operatorname{opt}_q(J)\le\rho_\Pi+\eta,\qquad v_{\mathrm{loc}}:= \sum_c\omega_c\mathbb E_{X\sim\mu_c}\overline{P_0}(X) \ge1-\eta. The local laws have common feasible Gram data for the relaxation in [GuruswamiEtAl2011OrderingCSP, Section 8.3]: there are a unit vector II and vectors bu,jb_{u,j}, u∈U,j∈[m]u\in U,j\in[m], with ∑jbu,j=I,⟨bu,i,bu,j⟩=0 (i≠j),∥bu,j∥2=1m, \sum_j b_{u,j}=I,\quad \langle b_{u,i},b_{u,j}\rangle=0\ (i\ne j),\quad \|b_{u,j}\|^2=\frac1m, and, for every two positions r,sr,s of cc, ⟨buc,r,i,buc,s,j⟩=Pr⁡X∼μc[Xr=i, Xs=j]. \langle b_{u_{c,r},i},b_{u_{c,s},j}\rangle =\Pr_{X\sim\mu_c}[X_r=i,\ X_s=j]. All these data are fixed by k,Π,q,ηk,\Pi,q,\eta.

In plain English

For every q≥1q\ge1 and rational η>0\eta>0 there is a finite local instance J=(U,C,ω)J=(U,\mathcal C,\omega) with ∣U∣=m≥2|U|=m\ge2, and rational laws μc\mu_c on [m]k[m]^k with uniform one-position marginals and all atoms above some α∈(0,1/2]\alpha\in(0,1/2]. The instance has opt⁡q(J)≤ρΠ+η\operatorname{opt}_q(J)\le\rho_\Pi+\eta while the local laws achieve value vloc≥1−ηv_{\mathrm{loc}}\ge1-\eta, and the laws come with common feasible Gram vectors II and bu,jb_{u,j} for the ordering-CSP relaxation whose inner products equal the pairwise marginals of μc\mu_c.

Why it's here

This is the finite gadget on which the ordering transfer is built: it supplies a local instance that is nearly as hard as random for qq-valued assignments but whose local distributions are almost perfectly satisfying, together with the vector (Gram) data realizing those distributions. The transfer proposition uses it for completeness via vlocv_{\mathrm{loc}} and soundness via opt⁡q\operatorname{opt}_q, and the rounding lemma uses the Gram data and the lower bound α\alpha to build a Gaussian ensemble matching the local moments. All the data depend only on k,Π,q,ηk,\Pi,q,\eta.
Classified routine:
This adapts the integrality-gap construction for ordering CSPs relaxed to q-valued CSPs in Guruswami, Håstad, Manokaran, Raghavendra and Charikar (2011, Section 8.3). It repackages their local instance and SDP vectors with the finiteness, rationality and lower-bound-α properties needed for the transfer.

Uses

Nothing else in the paper

Used by

propFinite ordering transfer from Unique GameslemLow-influence functions cannot beat opt_q(J)claimCoarse completeness in independent neighbor experimentclaimParameter choices give final ordering gapclaimCommon Gaussian ensemble matching local moments

Sources

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

Phase 2 aligns this node to a Lean declaration.