propositionroutineunresolved_ref

Finite ordering transfer from Unique Games

Maps strong-left Unique Games to ordering CSPs with gap 1−δ1-\delta vs ρΠ+δ\rho_\Pi+\delta
reduction behind the ordering-CSP hardness
Proposition·prop:finite-ordering-transfer·§A.2 The finite ordering transfer

Statement (paper)

Fix k≥2k\ge2 and ∅≠Π⊊Sk\varnothing\ne\Pi\subsetneq S_k, put ρΠ=∣Π∣/k!\rho_\Pi=|\Pi|/k!, and fix 0<δ<(1−ρΠ)/20<\delta<(1-\rho_\Pi)/2. There are integers q,H≥1q,H\ge1 and positive rationals ζ,ν<1\zeta,\nu<1, depending only on k,Π,δk,\Pi,\delta, with the following property for every fixed integer R≥1R\ge1. Let Φ=(A,B,E)\Phi=(A,B,E) be a nonempty explicit unweighted simple bipartite Unique Games instance over [R][R], oriented from AA to BB, whose common left degree hh satisfies h≥Hh\ge H and q∣hq\mid h. There is a deterministic transformation, polynomial in the explicit size of Φ\Phi for fixed RR, producing an explicit list of Π\Pi-ordering constraints on distinct variables within each constraint, with nonnegative rational weights, each encoded by a binary numerator and a positive binary denominator, summing to one. If some labeling strongly satisfies at least (1−ζ)∣A∣(1-\zeta)|A| left vertices, then OPT⁡Π(I)≥1−δ\OPT_\Pi(I)\ge1-\delta. If val⁡(Φ)≤ν\val(\Phi)\le\nu, then OPT⁡Π(I)≤ρΠ+δ\OPT_\Pi(I)\le\rho_\Pi+\delta. The constants q,H,ζ,νq,H,\zeta,\nu are independent of both RR and hh.

In plain English

For fixed kk, a nonempty proper Π⊊Sk\Pi\subsetneq S_k and small δ\delta, there are constants q,H,ζ,νq,H,\zeta,\nu and a deterministic polynomial-time map from simple bipartite Unique Games instances over [R][R] with left degree h≥Hh\ge H, q∣hq\mid h, to weighted Π\Pi-ordering instances. If a labeling strongly satisfies (1−ζ)∣A∣(1-\zeta)|A| left vertices, the ordering optimum is at least 1−δ1-\delta; if val⁡(Φ)≤ν\val(\Phi)\le\nu, it is at most ρΠ+δ\rho_\Pi+\delta.

Why it's here

This is the main reduction behind the ordering-CSP hardness consequence. It combines the strong-left Unique Games instances with the finite local gadget, using the rounding and collision lemmas for soundness and the local laws for completeness. The constants do not depend on RR or hh, so the Unique Games Theorem's alphabet can be plugged in directly to get an explicit weighted ordering instance with a 1−δ1-\delta versus ρΠ+δ\rho_\Pi+\delta gap.
Classified routine:
Adapts the known UG-hardness reduction for ordering CSPs (Guruswami–Håstad–Manokaran–Raghavendra–Charikar, Every permutation CSP of arity 3 is approximation resistant / Beating the random ordering is hard) to the paper's strong-left UG instances, assembled from the earlier gadget, rounding and collision lemmas.

Uses

lemFinite local ordering instance with Gram datalemLow-influence functions cannot beat opt_q(J)lemLow-influence functions rarely collide under couplinglemUnique Games with constant left degree and strong satisfactionthmThe Unique Games Theorem

Used by

corOptimal hardness for ordering CSPs

Inside the proof

claimCoarse completeness in independent neighbor experimentclaimBlock functions are simplex-valued, low influenceclaimPseudorandom vertices have local payoff boundclaimFew influential coordinates per right vertexclaimNonpseudorandom excess decodes to game labelingclaimConditioning on distinct neighbors gives strict gapclaimParameter choices give final ordering gapclaimExplicit rational encoding is polynomial

Sources

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

Phase 2 aligns this node to a Lean declaration.

Friction

  • warn
    unresolved_ref
    Bound on influential coordinates per right vertex is imported from Guruswami et al. Lemma 4.3.