corollaryroutine

Optimal hardness for ordering CSPs

So ordering CSPs are NP-hard at 1−ε1-\varepsilon vs ρΠ+ε\rho_\Pi+\varepsilon
payoff of the main theorem
Corollary·cor:ordering-csp·§8.2 Ordering constraints

Statement (paper)

Fix k≥2k\ge2 and ∅≠Π⊊Sk\varnothing\ne\Pi\subsetneq S_k, and put ρΠ=∣Π∣/k!\rho_\Pi=|\Pi|/k!. For every fixed 0<ε<(1−ρΠ)/20<\varepsilon<(1-\rho_\Pi)/2, it is NP-hard to distinguish finite weighted Π\Pi-ordering-CSP instances II satisfying OPT⁡Π(I)≥1−εfrom those satisfyingOPT⁡Π(I)≤ρΠ+ε. \OPT_\Pi(I)\ge1-\varepsilon \qquad\text{from those satisfying}\qquad \OPT_\Pi(I)\le\rho_\Pi+\varepsilon. Consequently, approximation at every fixed ratio r∈(ρΠ,1]r\in(\rho_\Pi,1] is NP-hard. Together with the random-ordering guarantee, this gives the optimal threshold ρΠ\rho_\Pi.

In plain English

For fixed k≥2k\ge2 and a nonempty proper Π⊊Sk\Pi\subsetneq S_k with ρΠ=∣Π∣/k!\rho_\Pi=|\Pi|/k!, and any fixed 0<ε<(1−ρΠ)/20<\varepsilon<(1-\rho_\Pi)/2, it is NP-hard to distinguish weighted Π\Pi-ordering-CSP instances with optimum at least 1−ε1-\varepsilon from those with optimum at most ρΠ+ε\rho_\Pi+\varepsilon. Hence approximating within any fixed ratio r∈(ρΠ,1]r\in(\rho_\Pi,1] is NP-hard, so the random-ordering threshold ρΠ\rho_\Pi is optimal.

Why it's here

This is the final hardness consequence for ordering constraints. It composes the Unique Games Theorem with the strong-left, constant-degree Unique Games form and then the finite ordering transfer, taking δ=ε\delta=\varepsilon. The transfer's constants do not depend on the alphabet size RR or the degree hh, so the Unique Games alphabet can be plugged in directly. The result gives a completeness versus soundness gap of 1−ε1-\varepsilon versus ρΠ+ε\rho_\Pi+\varepsilon, which matches the trivial random-ordering guarantee.
Classified routine:
Direct composition of the Unique Games Theorem with the strong-left constant-degree UG form and the finite ordering transfer. It mirrors the known UGC-conditional ordering-CSP hardness of Guruswami–Håstad–Manokaran–Raghavendra–Charikar, which becomes unconditional once the UG Theorem is available.

Uses

propFinite ordering transfer from Unique GameslemUnique Games with constant left degree and strong satisfactionthmThe Unique Games Theorem

Used by

Nothing in the paper

Sources

PaperOpen
Section
§8.2 Ordering constraints
Page
—
Label
cor:ordering-csp
Line
sections/07-consequences.tex:190
Leannot aligned

Phase 2 aligns this node to a Lean declaration.