Gate constraints are a weak assignment tester

The gadget. Put ${\mathrm{\Sigma }}_0:=\{0,1{\}}^3$, with designated symbols $0=(0,0,0)$ and $1=(1,1,1)$; the remaining six symbols are auxiliary. Take as vertices the $s+m$ wires of $C$, listed in a topological order, together with one gate vertex per non-input gate; the wire vertices include the named input coordinates and are the only vertices whose alphabet is restricted to the two designated symbols. For each wire vertex $v$ add one loop edge with relation $D:=\{(s,s):s\in \{0,1\}\}$, restricting its label to a designated symbol. Write $d(0):=(0,0,0)$ and $d(1):=(1,1,1)$ for the designated symbols. For a gate $g$ with input wires $p,q$ and output wire $r$ let $T_g\subseteq {\mathrm{\Sigma }}_0$ be the set of triples $(a,b,z)$ with $z$ the value of $g$ on the input bits $a,b$, taking $b:=a$ and $p=q$ for the one-input gate NOT, so that $T_g$ is a four-element table for AND and OR and the two-element table $\{(a,a,1-a):a\in \{0,1\}\}$ for NOT; for a constant gate let $T_g:=\{(c,c,c)\}$ and let $r$ be its output wire. Add a loop edge at the gate vertex with relation $D_g:=\{(s,s):s\in T_g\}$, add edges from the gate vertex to $p$ and to $q$ with relations $P_1:=\{((a,b,z),d(a)):(a,b,z)\in T_g\}$ and $P_2:=\{((a,b,z),d(b)):(a,b,z)\in T_g\}$, and add an edge from the gate vertex to $r$ with relation $P_3:=\{((a,b,z),d(z)):(a,b,z)\in T_g\}$; for a constant gate only $P_3$ is added, there being no input wire. Finally add a loop at the output wire with relation $\{(1,1)\}$.

Size and explicitness. Each wire contributes one loop, each non-constant gate contributes one loop and three projection edges, each constant gate one loop and one projection edge, and the output one further loop; hence $M\le (s+m)+4m+1=O(m+s)$ ordinary edges, and ${\mathrm{\Sigma }}_0$ is a fixed eight-symbol alphabet with relations of at most $8\times 8$ entries. Every relation is one of the finitely many displayed tables determined by the gate type, so the edge list is written down from the topological gate list in time linear in $m+s$.

Perfect completeness. If $x\in \mathrm{SAT}(C)$, choose an assignment to the other $s-n$ input coordinates witnessing acceptance, and label every wire vertex by its value in the resulting evaluation of $C$, read as the designated symbol $0$ or $1$, and label each gate vertex by the triple of the two input values and the output value of that gate. Then every wire label is designated, so the loops with relation $D$ are satisfied; each gate vertex carries a triple of its truth table, so its loop $D_g$ is satisfied; each projection edge is satisfied because the triple's coordinates are exactly the labels of the corresponding wire vertices; and the output loop is satisfied because the output evaluates to $1$. Hence ${\mathrm{UNSAT}}_{x\cup b}(G)=0$ for that labeling, the completeness clause of [F3].

Soundness. Fix $x\in \{0,1{\}}^X$ and an arbitrary labeling $b$ of the gate vertices and of the wire vertices other than the named inputs, and suppose all $M$ edges of $G$ are satisfied. Then every wire label is a designated symbol by the loops with relation $D$. Read the labels of the unnamed input wires as an assignment to the other $s-n$ input coordinates. We show by induction along the topological order that each wire label equals the evaluation of that wire on this full input assignment: the input vertices have these values by construction, and for a gate whose input wires are already correct, its loop forces its label to be a truth-table triple $(a,b,z)$ of that gate, while the projection edges force $a$ and $b$ to be the labels of its input wires and $z$ to be the label of its output wire; hence the output wire of the gate carries the correct evaluated value. The induction terminates at the designated output wire, whose loop forces its label to be $1$, so the output evaluates to $1$ and $C$ accepts $x$ by [F1]. Therefore if $x\mathrm{\notin }\mathrm{SAT}(C)$ at least one edge is violated under every $b$, that is ${\mathrm{UNSAT}}_{x\cup b}(G)\ge 1\mathrm{/}M$; and since $\delta (x,\mathrm{SAT}(C))\le 1$ always, with $\delta =1$ on $\mathrm{SAT}(C)=\mathrm{\varnothing }$ by [F3], this gives ${\mathrm{UNSAT}}_{x\cup b}(G)\ge \delta (x,\mathrm{SAT}(C))\mathrm{/}M$.

Steps 2.1, 2.2 and 2.3 verify the size, explicitness, completeness and instancewise soundness clauses with ${\rho }_C=1\mathrm{/}M$, for the constructed graph over ${\mathrm{\Sigma }}_0=\{0,1{\}}^3$ of arity $2$, the input coordinates being the wire vertices of the named inputs labeled by the designated symbols. Since $M$ is unbounded across circuits, this is a weak, size-dependent proximity construction rather than a map with the fixed rejection ratio required by [F3].