Constraint cloud rounding and loop counts

Given: the objects and hypotheses in the statement above.

Let $G$ have $m=\mathrm{\mid }E\mathrm{\mid }>0$ ordinary edges, with the fixed nonempty alphabet and paired-loop convention. Its cloud graph $G_1$ is degree $129$, has $2m$ vertices and $129m$ ordinary edges, and is constructible in polynomial time without changing the alphabet. Put $K=\max (1,2\mathrm{/}{h}_0)=20\mathrm{/}7$ and $c=1\mathrm{/}(129K)$. Then $c\mathrm{UNSAT}(G)\le \mathrm{UNSAT}(G_1)\le \mathrm{UNSAT}(G)\mathrm{/}129.$ For every labeling $\tau$ of $G_1$, plurality decoding $D\tau$ satisfies ${\mathrm{UNSAT}}_{D\tau }(G)\le 129K{\mathrm{UNSAT}}_{\tau }(G_1)$. For an edgeless input use the empty output convention and UNSAT zero. (Regularization preserves value quantitatively).

For $G$ with $m>0$ edges, the full preprocessing graph $G_2$ has $2m$ vertices, degree $387$, and $387m$ ordinary edges over the same alphabet. It has loops at every vertex and $\alpha (G_2)\le {\rho }_2:=\frac{259+128{\rho }_0}{387}<1.$ With $K=20\mathrm{/}7$ and $c=1\mathrm{/}(129K)$, $\frac{129c}{387}\mathrm{UNSAT}(G)\le \mathrm{UNSAT}(G_2)\le \frac{\mathrm{UNSAT}(G)}{387}\mathrm{.}$ For every port labeling $\tau$, ${\mathrm{UNSAT}}_{\tau }(G_2)=(129\mathrm{/}387){\mathrm{UNSAT}}_{\tau }(G_1)$ and ${\mathrm{UNSAT}}_{D\tau }(G)\le 387K{\mathrm{UNSAT}}_{\tau }(G_2)$. Construction and plurality decoding take polynomial time. The edgeless convention has UNSAT zero. (Constraint expander overlay).