claimroutine
Padding predicates to common arity
Padding predicates to a common arity leaves OPT and the SDP unchanged
normalizes for Raghavendra's theorem
Claim·§8.1 Constraint satisfaction and Vertex Cover·inside corGap hardness from a fixed SDP integrality gap
Statement (paper)
Identify with a fixed and pad every predicate of with ignored trailing arguments to a common positive arity, filling the added positions with a fixed variable of . Then each applied payoff and its dependence set is unchanged, so and the relaxation of [RaghavendraThesis09, Section 4.5] are preserved, and each local distribution in that relaxation is over assignments to the variables on which its applied payoff actually depends.
In plain English
After identifying the domain with a fixed , every predicate of can be padded with ignored trailing arguments (filled by a fixed variable of ) to a common positive arity, without changing or the relaxation . Each local distribution in the relaxation is still over the variables its applied payoff actually depends on.
Why it's here
This is a normalization step that puts into the uniform-arity, domain- form required to apply Raghavendra's framework to the fixed instance . Because the padded positions are ignored, each payoff and its dependence set are unchanged, so the gap for carries over, and the later claim can invoke Raghavendra's fixed-instance theorem.
Classified routine:
A standard normalization (padding predicates with dummy arguments to a uniform arity over domain [q]) checked directly against the definition of the relaxation in Raghavendra's thesis (Section 4.5). Padding leaves every payoff and its dependence set unchanged, so OPT and SDP_R are preserved.
Uses
Nothing else in the paper
Used by
Sources
PaperOpen
- Section
- §8.1 Constraint satisfaction and Vertex Cover
- Page
- —
- Label
—- Line
sections/07-consequences.tex:76
Leannot aligned
Phase 2 aligns this node to a Lean declaration.