Gap Amplification and Assignment Testing

Throughout this page a binary constraint graph is one in the convention of Constraint graph and labeling value: a finite ordinary undirected multigraph with paired incidence slots, a finite nonempty alphabet $\mathrm{\Sigma }$, one relation $R_e\subseteq {\mathrm{\Sigma }}^2$ per edge in a specified endpoint order, and explicit Boolean relation tables. For an edge set $E\mathrm{\ne }\mathrm{\varnothing }$ the value ${\mathrm{val}}_{\sigma }(G)$ is the fraction of ordinary edges satisfied by the labeling $\sigma$, and $\mathrm{UNSAT}(G)={\min }_{\sigma }(1-{\mathrm{val}}_{\sigma }(G))$; an edgeless graph has value one and unsatisfiability zero, as in the published convention. The explicit encoding of $G$ is the list of vertices, the paired incidence slots, the alphabet size and the relation tables; its bit length is the input size of the algorithms below.

Fix an alphabet-size parameter $s\ge 1$ and a degree parameter $d\ge 1$ for the input graphs. A complete uniform gap-preserving reduction with output alphabet ${\mathrm{\Sigma }}^{\mathrm{\prime }}$, output degree bound $d^{\mathrm{\prime }}$, blowup $C$ and gap map $g$ consists of a deterministic algorithm $R$ that, given the explicit encoding of a binary constraint graph $G$ over an alphabet $\mathrm{\Sigma }$ with $\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }=s$ whose underlying graph has all vertex degrees at most $d$, outputs the explicit encoding of a binary constraint graph $R(G)$ over the fixed alphabet ${\mathrm{\Sigma }}^{\mathrm{\prime }}$ such that:

1. Output shape. Arity stays two, all vertex degrees of $R(G)$ are at most $d^{\mathrm{\prime }}$, and $\mathrm{\mid }E(R(G))\mathrm{\mid }\le C\mathrm{\mid }E(G)\mathrm{\mid },\mathrm{\mid }V(R(G))\mathrm{\mid }\le C\mathrm{\mid }E(G)\mathrm{\mid }\text{ whenever }E(G)\mathrm{\ne }\mathrm{\varnothing }\mathrm{.}$ An edgeless input is mapped to an edgeless output, which therefore has value one.
2. Completeness. $\mathrm{UNSAT}(G)=0$ implies $\mathrm{UNSAT}(R(G))=0$.
3. Gap preservation. $\mathrm{UNSAT}(R(G))\ge g(\mathrm{UNSAT}(G))$ for every input $G$, where $g:[0,1]\to [0,1]$ is nondecreasing with $g(0)=0$ and $g(\epsilon )>0$ for every $\epsilon >0$.
4. Uniformity. $R$ runs in time polynomial in the bit length of the explicit input encoding, and the output is explicit. The alphabet ${\mathrm{\Sigma }}^{\mathrm{\prime }}$, the numbers $d^{\mathrm{\prime }}$, $C$ and the function $g$ depend only on the fixed parameters $s,d$ and on $R$ itself, never on $\mathrm{\mid }V(G)\mathrm{\mid }$ or $\mathrm{\mid }E(G)\mathrm{\mid }$.

The definition asserts no existence statement: it records the interface in which the degree-reduction, powering and assignment-tester steps of this page are stated. Isolated vertices may be deleted from inputs and outputs without changing value or unsatisfiability, so the vertex bound in clause 1 is never needed for padded inputs; the bounded-degree clause and the fixed alphabet keep the explicit encoding length of the output within a constant multiple of $\mathrm{\mid }V(R(G))\mathrm{\mid }+\mathrm{\mid }E(R(G))\mathrm{\mid }$ plus logarithmic vertex names. Loops count as ordinary edges with two incidences and a relation tested on the repeated label, exactly as published. Monotonicity of $g$ is used only to compose gap maps, in Complete linear-blowup reductions compose, never to enlarge an input hypothesis.

Let $R_1$ be a complete uniform gap-preserving reduction with output alphabet ${\mathrm{\Sigma }}_1$, output degree bound $d_1$, blowup $C_1$ and gap map $g_1$, defined for input alphabets of size $s$ and input degrees at most $d$. Assume also that $R_1(G)$ has at least one edge whenever $G$ has at least one edge. Let $R_2$ be a complete uniform gap-preserving reduction with output alphabet ${\mathrm{\Sigma }}_2$, output degree bound $d_2$, blowup $C_2$ and gap map $g_2$, defined for input alphabets of size at least $\mathrm{\mid }{\mathrm{\Sigma }}_1\mathrm{\mid }$ and input degrees at most $d_1$. Then the composition $R_2\circ R_1$, which on input $G$ first computes $R_1(G)$ and then $R_2(R_1(G))$, is a complete uniform gap-preserving reduction for input alphabets of size $s$ and input degrees at most $d$, with output alphabet ${\mathrm{\Sigma }}_2$, output degree bound $d_2$, blowup $C_1{C}_2$, gap map $g_2\circ g_1$, and running time polynomial in the bit length of the explicit input encoding of $G$.

• The compatibility hypotheses are not cosmetic: $R_2$ is applied to a graph whose alphabet is ${\mathrm{\Sigma }}_1$ and whose degrees are bounded by $d_1$, and step 1.1 is exactly where those two fixed parameters, together with the edge bound, keep the intermediate explicit encoding polynomially short. Without a bound on the intermediate encoding length the composition of two polynomial-time algorithms need not be polynomial time in the original input length.
• The edge blowup multiplies and the gap maps compose in the order the reductions are applied; no constant is lost. Later items of this page use the lemma with $R_1$ the degree-reduction map and $R_2$ the powering map.

Fix the alphabet $\mathrm{\Sigma }$ of Constraint graph and labeling value, a total ordering of $\mathrm{\Sigma }$ used for plurality tie breaking, and the reverse-paired degree-$128$ expander family $H_r$ with unnormalized edge expansion at least $h_0=7\mathrm{/}10$ for $r\ge 2$ that is used in Constraint graph regularization.

Let $G$ be a binary constraint graph over $\mathrm{\Sigma }$ in the published convention. The degree-reduction map $R_{\mathrm{deg}}$ is the following deterministic construction, which is the published cloud-and-overlay preprocessing read as a map on explicit encodings.

1. If $E(G)=\mathrm{\varnothing }$, output the empty graph over $\mathrm{\Sigma }$, which has value one.
2. Otherwise delete isolated vertices, and replace every vertex $v$ of degree $r$ by a cloud of its $r$ incidence ports, so that each original edge contributes its two distinct ports, a loop contributing two distinct ports at its vertex. Put a copy of $H_r$ inside the cloud, with equality relations on all its edges, and keep one external edge for each original edge, joining its two designated ports and carrying the same relation in the same endpoint order. The result is the cloud graph $G_1$ of Constraint expander overlay; it has degree $129$ and $2\mathrm{\mid }E(G)\mathrm{\mid }$ vertices.
3. On the $2\mathrm{\mid }E(G)\mathrm{\mid }$ ports add a copy of $H_{2\mathrm{\mid }E(G)\mathrm{\mid }}$ with tautological relations and $65$ ordinary tautological loops at every port, i.e. $130$ loop slots, to obtain the registered graph $G_2$. By the published count, $G_2$ is $387$-regular with $2\mathrm{\mid }E(G)\mathrm{\mid }$ vertices and $387\mathrm{\mid }E(G)\mathrm{\mid }$ ordinary edges, its normalized adjacency satisfies $\alpha (G_2)\le {\rho }_2=(259+128{\rho }_0)\mathrm{/}387<1$, and its alphabet is still $\mathrm{\Sigma }$.

The decoding map $D$ sends a labeling $\tau$ of $G_2$ (equivalently of $G_1$, on which it depends only through the ports) to the labeling $D\tau$ of $G$ that assigns to each original vertex the most frequent label among the ports of its cloud, breaking ties by the fixed ordering; deleted isolated vertices receive the first symbol of $\mathrm{\Sigma }$. This is the plurality decoding of Constraint graph regularization.

Every step is a fixed function of the explicit input encoding: listing the $H_r$ adjacency lists, copying $2\mathrm{\mid }E(G)\mathrm{\mid }$ relation tables and adding $387\mathrm{\mid }E(G)\mathrm{\mid }$ tautological slots takes time and output length polynomial in the input encoding length, and the output parameters $2\mathrm{\mid }E(G)\mathrm{\mid }$, $387\mathrm{\mid }E(G)\mathrm{\mid }$, $387$, ${\rho }_2$ depend only on the fixed family and on $\mathrm{\mid }E(G)\mathrm{\mid }$. The map is the first of the two transformations composed in A complete uniform graph gap-amplification step; its quantitative unsatisfiability guarantee is stated and proved there, not here.

Let $G$ be a binary constraint graph over the fixed alphabet $\mathrm{\Sigma }$ with $E(G)\mathrm{\ne }\mathrm{\varnothing }$, let $G_1$ be its cloud graph as constructed by the degree-reduction map Degree reduction by expander incidence clouds, and let $\tau$ be any labeling of the ports of $G_1$ with corresponding plurality decoding $\sigma =D\tau$. Write $S$ for the number of ports whose label differs from the decoded label $\sigma (v)$ of their original vertex $v$, and let $U_{\mathrm{i}\mathrm{n}\mathrm{t}}$ and $U_{\mathrm{e}\mathrm{x}\mathrm{t}}$ count the equality edges inside clouds and the external edges that are violated by $\tau$. Then $U_{\mathrm{i}\mathrm{n}\mathrm{t}}\ge \frac{7}{20}S,U_G\le U_{\mathrm{e}\mathrm{x}\mathrm{t}}+S,$ where $U_G$ is the number of ordinary edges of $G$ violated by the decoded labeling $\sigma$.

• This item is the page-local interface of the published rounding bound: its content is the published argument of Cloud plurality rounding, cited here with the page's notation, not re-derived. It lets Degree reduction preserves unsatisfaction quantitatively cite the cloud decoding estimate by ID without restating the construction.
• The hypothesis $E(G)\mathrm{\ne }\mathrm{\varnothing }$ is inherited from the cloud construction: the edgeless input is handled by the separate empty-output convention of Degree reduction by expander incidence clouds, where there are no clouds and both sides of each inequality are zero.

Let $G$ be a binary constraint graph over the fixed alphabet $\mathrm{\Sigma }$ with $E(G)\mathrm{\ne }\mathrm{\varnothing }$, and let $G_2=R_{\mathrm{deg}}(G)$ be its degree-reduced graph as constructed by Degree reduction by expander incidence clouds. Then $G_2$ is $387$-regular over the same alphabet, has $2\mathrm{\mid }E(G)\mathrm{\mid }$ vertices and exactly $387\mathrm{\mid }E(G)\mathrm{\mid }$ ordinary edges, is produced from the explicit encoding of $G$ by a deterministic algorithm in polynomial time, and with $K=20\mathrm{/}7$ its unsatisfiability satisfies perfect completeness and the quantitative bound $\mathrm{UNSAT}(G_2)\ge \frac{\mathrm{UNSAT}(G)}{387K}=\frac{7}{7740}\mathrm{UNSAT}(G)\mathrm{.}$ Consequently $R_{\mathrm{deg}}$, with the empty output on edgeless inputs, is a complete uniform gap-preserving reduction in the sense of Complete uniform gap-preserving CSP reductions with output alphabet $\mathrm{\Sigma }$, output degree bound $387$, blowup $387$ and gap map $g(\epsilon )=\epsilon \mathrm{/}(387K)$.

• The constant is not improvable by this proof: the factor $387K=7740\mathrm{/}7$ is exactly the loss accumulated by the cloud rounding inequality $U_G\le U_{\mathrm{e}\mathrm{x}\mathrm{t}}+(2\mathrm{/}{h}_0)U_{\mathrm{i}\mathrm{n}\mathrm{t}}$ and the uniform edge rescaling from $129m$ to $387m$ slots in [F1]. Later items absorb it into their own constants, which is why A complete uniform graph gap-amplification step carries a smaller $\beta$.
• Fact [F2] is declared because the published derivation of the decoding inequality in [F1] runs through the cloud rounding bound; the page records that bound as its own interface so that the code and tester branches can cite it.

Let $G$ be a binary constraint graph over the alphabet $\mathrm{\Sigma }$ in the convention of Constraint graph and labeling value, whose underlying graph is $d$-regular in the adjacency-slot convention of Regular multigraph and normalized adjacency, and let $t\ge 1$ be an integer. Put $R:=t+\lceil \sqrt{t}\rceil ,L:=2t+1.$ A lazy step at a vertex $v$ is the choice of one of the $2d$ options: one of $d$ hold options (the walk stays at $v$) or one of the $d$ slots at $v$ (the walk traverses that slot). A lazy walk of length $\mathrm{\ell }$ is a sequence of $\mathrm{\ell }$ independent uniform lazy steps; its transition matrix is $(I+M)\mathrm{/}2$ with $M$ the normalized adjacency of the graph, so each step holds with probability $1\mathrm{/}2$ and otherwise traverses a uniformly chosen slot. Since the graph is regular, the uniform distribution on $V$ is stationary, and the count of lazy walk patterns of length $\mathrm{\ell }$ starting at $v$ is $(2d{)}^{\mathrm{\ell }}$.

Write ${\mathcal{P}}_{\mathrm{\ell }}:=\{1,\dots ,2d{\}}^{\mathrm{\ell }}$ for the set of lazy-walk patterns of length $\mathrm{\ell }$, a set of cardinality $(2d{)}^{\mathrm{\ell }}$ independent of the starting vertex. A pattern read from a vertex determines the sequence of visited vertices and the slots traversed. The local-view alphabet of the powering is ${\mathrm{\Sigma }}_t:={\mathrm{\Sigma }}^{{\mathcal{P}}_R},$ that is, a view is a function assigning a symbol of $\mathrm{\Sigma }$ to every length-$R$ pattern. Fix the lexicographic order on patterns induced by the option order. For vertices $x,y$ at graph distance at most $R$, let ${\kappa }_{x,y}\in {\mathcal{P}}_R$ be the lexicographically first pattern read from $x$ that ends at $y$; this set is nonempty because a path of length at most $R$ can be padded by holds. Its cardinality is $\mathrm{\mid }{\mathrm{\Sigma }}_t\mathrm{\mid }=\mathrm{\mid }\mathrm{\Sigma }{\mathrm{\mid }}^{(2d{)}^R}\le \mathrm{\mid }\mathrm{\Sigma }{\mathrm{\mid }}^{(2d{)}^{O(t)}}$.

The powered graph $G_t$. Its vertex set is $V$; the label of a vertex $v$ is a view ${\phi }_v\in {\mathrm{\Sigma }}_t$. For every length-$L$ pattern $\sigma =({\sigma }_1,\dots ,{\sigma }_L)\in {\mathcal{P}}_L$, starting vertex $v_0\in V$, and copy bit $b\in \{0,1\}$, create a directed incidence slot; reading $\sigma$ from $v_0$ gives the visited vertices $v_0,v_1,\dots ,v_L$, and the slot joins $v_0$ to $v_L$. Pair it with the slot for the reversed pattern read from $v_L$ and copy bit $1-b$. This fixed-point-free pairing duplicates every walk slot, as required to represent the adjacency-slot power as an ordinary undirected multigraph even when a walk is fixed by reversal. The relation table in the orientation $(v_0,v_L)$ is the one given below; the paired reverse orientation carries its transpose. Let $J:=\{j:1\le j\le L,j-1\le R,L-j\le R\}$ be the central window of positions, of size $2\lceil \sqrt{t}\rceil +1$, symmetric about the midpoint $t+1$. The edge relation in the orientation of the pattern $\sigma$ from $v_0$ to $v_L$ consists of all pairs $(\phi ,\psi )\in {\mathrm{\Sigma }}_t^2$ such that for every $j\in J$ whose step ${\sigma }_j$ is a move along a slot $e=(v_{j-1},v_j)$ of $G$, the pair $(\phi ({\kappa }_{v_0,v_{j-1}}),\psi ({\kappa }_{v_L,v_j}))$ belongs to the relation of $e$ in its orientation $(v_{j-1},v_j)$. The canonical patterns exist because $j-1\le R$ and $L-j\le R$, so both endpoints lie within radius $R$ of their respective view centres. Hold steps impose no condition.

Every vertex has exactly $2(2d{)}^L$ incident slots, so $G_t$ is $d_t$-regular with $d_t=2(2d{)}^L$. The pairing gives $\mathrm{\mid }V\mathrm{\mid }(2d{)}^L$ ordinary edges and the same number of relation tables, equivalently $2\mathrm{\mid }V\mathrm{\mid }(2d{)}^L$ directed incidence slots. Sampling a uniform ordinary edge and orienting it by its unique copy-$0$ incidence slot is therefore equivalent to choosing a uniform start vertex and a uniform length-$L$ pattern; its violation probability is ${\mathrm{UNSAT}}_{\phi }(G_t)$. Since $d$ and $t$ are fixed, ${\mathrm{\Sigma }}_t$ is a fixed finite alphabet; each table is a subset of the fixed finite set ${\mathrm{\Sigma }}_t^2$, computable by the displayed rule, so the number of table entries is $O_{d,t,\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }}(\mathrm{\mid }V\mathrm{\mid }(2d{)}^L)$, while endpoint names and paired-slot indices require $O_{d,t}(\log (\mathrm{\mid }V\mathrm{\mid }+2))$ bits each. Thus the explicit bit encoding has length $O_{d,t,\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }}(\mathrm{\mid }V\mathrm{\mid }(2d{)}^L\log (\mathrm{\mid }V\mathrm{\mid }+2))$. Enumerating the patterns, computing their endpoints and canonical coordinates, and writing the fixed-size relation tables takes time polynomial in the explicit input and output bit lengths.

• Convention bridge. This is the Arora-Barak §18.5.1 convention: views cover the ball of radius $t+\lceil \sqrt{t}\rceil$, powered slots are length-$(2t+1)$ walks, and the central window has $2\lceil \sqrt{t}\rceil +1$ positions. Dinur's §6 uses walks of length $t$ with views of radius $\lceil t\mathrm{/}2\rceil$ and a window of $\sqrt{t}$ positions. The two parameterizations are translations of one another, but their numerical constants are not interchangeable; every later item on this page states its bounds in the present convention, and the lazy walk introduced here is the one used throughout.
• The reversal pairing is consistent with the published endpoint convention: position $j$ reverses to $L+1-j\in J$, the endpoint views swap, and each tested base relation is transposed. Thus the reverse-pattern table is the transpose of the original table, exactly as Constraint graph and labeling value requires. If a walk pattern is fixed by reversal, its central option is a hold and the mirrored move tests pair in transposed pairs; its table is therefore symmetric, so the two copy-bit incidences define one well-formed loop edge.
• Each view records one canonical coordinate for each vertex of the radius-$R$ ball; a middle-position constraint reads those coordinates for the two endpoints of its tested base edge. The canonical coordinate removes any dependence on the placement of holds, while plurality decoding still counts distinct walk patterns with multiplicity.
• The role of this construction in the page is the powering step of A complete uniform graph gap-amplification step; the companion item Graph power and walk constraint records the underlying one-step power convention, in which a walk predicate is a conjunction of the original edge relations along the walk.

Let $G$ be a $d$-regular binary constraint graph over $\mathrm{\Sigma }$, let $t\ge 1$ and let $G_t$ be its powered graph as in Constraint graph powering with local-view labels. If $\sigma :V\to \mathrm{\Sigma }$ satisfies every edge of $G$, then the canonical lift $\bar{\sigma }$ defined by $\bar{\sigma }(v)(\pi ):=\sigma (\text{endpoint of the pattern }\pi \text{ read from }v),\pi \in {\mathcal{P}}_R,$ is a labeling of $G_t$ that satisfies every slot of $G_t$; in particular $\mathrm{val}(G_t)=1$ whenever $\mathrm{val}(G)=1$. The same holds with repeated vertices, hold steps and loops, and no hypothesis on $t$ beyond $t\ge 1$ is used.

• The lift is a function of the base labeling and the explicit pattern list; it makes no choice. Repeated occurrences of one vertex in a pattern all receive the same symbol $\sigma$ of that vertex, which is why consistency across the central overlap is automatic here.
• The converse direction is not claimed: satisfying labelings of $G_t$ need not be lifts. That gap is what the plurality decoding and collision analysis of the following items address.

Let $G$ be a binary constraint graph over the finite nonempty alphabet $\mathrm{\Sigma }$ whose underlying graph is $d$-regular in the adjacency-slot convention of Constraint graph and labeling value, let $t\ge 1$, and let $G_t$ be its local-view powered graph with view alphabet ${\mathrm{\Sigma }}_t={\mathrm{\Sigma }}^{{\mathcal{P}}_R}$, pattern sets ${\mathcal{P}}_{\mathrm{\ell }}=\{1,\dots ,2d{\}}^{\mathrm{\ell }}$, length $L=2t+1$ and central window $J$ as in Constraint graph powering with local-view labels. Fix once and for all a total order on $\mathrm{\Sigma }$, and write $\min$ below for the least element in that order.

Let $\phi :V\to {\mathrm{\Sigma }}_t$ be a labeling of $G_t$; its value $\phi (w)$ at a vertex $w$ is the view at $w$. For vertices $v,w$ with $\mathrm{dist}(v,w)\le R$, write ${\kappa }_{w,v}$ for the canonical length-$R$ pattern from $w$ to $v$ fixed in Constraint graph powering with local-view labels.

Claims. Let $1\le \mathrm{\ell }\le R$ and let $\pi \in {\mathcal{P}}_{\mathrm{\ell }}$ be a lazy-walk pattern read from $v$ that ends at $w$. Since $\mathrm{dist}(v,w)\le \mathrm{\ell }\le R$, the canonical pattern ${\kappa }_{w,v}$ exists, and the view at $w$ assigns it a symbol $\phi (w)({\kappa }_{w,v})\in \mathrm{\Sigma }$; we say that the view at $w$ claims the value $\phi (w)({\kappa }_{w,v})$ for $v$ via $\pi$. The claim depends on the endpoint $w$, not on the placement of holds in $\pi$.

Plurality decoding. For $v\in V$ and $a\in \mathrm{\Sigma }$ put $p_v(a):=\frac{1}{(2d{)}^t}\mathrm{\#}\{\pi \in {\mathcal{P}}_t:\text{the view at the endpoint of }\pi \text{ read from }v\text{ claims }a\text{ for }v\},$ the number of length-$t$ patterns from $v$ whose endpoint's view claims $a$ for $v$, divided by the total number $(2d{)}^t$ of such patterns. Equivalently, $p_v$ is the law of the claimed value for $v$: if a pattern is drawn uniformly at random from ${\mathcal{P}}_t$, the view at its endpoint claims $a$ for $v$ with probability $p_v(a)$. The plurality decoding of the powered labeling $\phi$ is the labeling $\widehat{\phi }:V\to \mathrm{\Sigma },\widehat{\phi }(v):=\min \{a\in \mathrm{\Sigma }:p_v(a)={\max }_{b\in \mathrm{\Sigma }}{p}_v(b)\},$ that is, the least symbol, in the fixed order on $\mathrm{\Sigma }$, that is claimed for $v$ with maximal probability. We call $\widehat{\phi }(v)$ the decoded label of $v$ and $p_v$ the opinion distribution of $v$.

• Patterns are counted with multiplicity. Distinct patterns with the same endpoint contribute separate votes, while repeated visits inside a single pattern do not create extra votes; no uniform vote over distinct centres is taken. This is Dinur's "popular opinion" [display (4) of §6] and the Arora-Barak "plurality assignment" of §18.5.1, both of which average the claim of the endpoint of a random walk of the decoding length, with multiplicities.
• Tie breaking is part of the definition. The order on $\mathrm{\Sigma }$ is fixed once on the page, so the decoding is a function of the powered labeling and of the fixed explicit data of $G_t$: it makes no choice, and it is computable from the explicit encoding of $G_t$ by counting patterns, since $(2d{)}^t$ is a constant once $d$ and $t$ are fixed.
• The relation and decoding use the same canonical coordinate. The decoding consults a view at $w$ only at ${\kappa }_{w,v}$, the same coordinate that a powered slot relation reads for the base vertex $v$ at a middle position. Distinct length-$t$ patterns with the same endpoint therefore contribute the same claim value but are still counted with their pattern multiplicity.
• The decoding is defined for every labeling of $G_t$, canonical lifts included: for the canonical lift $\bar{\sigma }$ of a base labeling $\sigma$, every pattern from $v$ ends at a vertex $w$ whose view claims $\sigma (v)$ for $v$, so $p_v$ is concentrated on $\sigma (v)$ and $\widehat{\bar{\sigma }}=\sigma$.

Let $G$ be a binary constraint graph over $\mathrm{\Sigma }$ whose underlying graph is $d$-regular in the adjacency-slot convention of Constraint graph and labeling value, and use the lazy-walk convention of Constraint graph powering with local-view labels: a lazy step at a vertex chooses uniformly among $2d$ options, the $d$ hold options and the $d$ slots at that vertex, and a lazy-walk pattern of length $\mathrm{\ell }$ is drawn uniformly from ${\mathcal{P}}_{\mathrm{\ell }}$. Put $C_0:=\frac{1}{\sqrt{2\pi }}<\frac{1}{2}\mathrm{.}$ For $\mathrm{\ell }\ge 1$ let $B_{\mathrm{\ell }}$ be the number of non-hold options of a uniformly random lazy-walk pattern of length $\mathrm{\ell }$ read from a vertex $v$; $B_{\mathrm{\ell }}\sim \mathrm{Bin}(\mathrm{\ell },\frac{1}{2})$ for every $v$. Then:

1. Binomial closeness. For all integers $m,m^{\mathrm{\prime }}\ge 1$ with $\mathrm{\mid }m-m^{\mathrm{\prime }}\mathrm{\mid }\le \sqrt{\min (m,m^{\mathrm{\prime }})}$, $\mathrm{TV}(\mathrm{Bin}(m,\frac{1}{2}),\mathrm{Bin}(m^{\mathrm{\prime }},\frac{1}{2}))\le C_0\frac{\mathrm{\mid }m-m^{\mathrm{\prime }}\mathrm{\mid }}{\sqrt{\min (m,m^{\mathrm{\prime }})}}\mathrm{.}$
2. Transfer to walk statistics. A lazy-walk pattern determines its endpoint from its sequence of non-hold options. For any fixed labeling $\phi$ of the powered graph $G_t$ with its fixed view radius $R=t+\lceil \sqrt{t}\rceil$ and lengths $1\le \mathrm{\ell },{\mathrm{\ell }}^{\mathrm{\prime }}\le R$, the view at that endpoint claims for its start the value at the canonical coordinate specified in Plurality decoding of powered local views. Thus the claimed value, like the endpoint, is a function of the non-hold option sequence alone. Let $X_{v,\mathrm{\ell }}$ denote the value claimed for $v$ by the view at the endpoint of a uniformly random lazy-walk pattern of length $\mathrm{\ell }$ from $v$. Then for $m=\min (\mathrm{\ell },{\mathrm{\ell }}^{\mathrm{\prime }})$ and $\mathrm{\mid }\mathrm{\ell }-{\mathrm{\ell }}^{\mathrm{\prime }}\mathrm{\mid }\le \sqrt{m}$, $\mathrm{TV}(X_{v,\mathrm{\ell }},X_{v,{\mathrm{\ell }}^{\mathrm{\prime }}})\le C_0\frac{\mathrm{\mid }\mathrm{\ell }-{\mathrm{\ell }}^{\mathrm{\prime }}\mathrm{\mid }}{\sqrt{m}},$ The same endpoint-law bound holds for arbitrary positive lengths satisfying the displayed window condition, without a radius restriction.
3. The window used by the powering analysis. If $t\ge 4$ and $\mathrm{\mid }\mathrm{\ell }-t\mathrm{\mid }\le \sqrt{t}\mathrm{/}(8C_0\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid })$, then $\mathrm{TV}(X_{v,t},X_{v,\mathrm{\ell }})\le 1\mathrm{/}(4\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid })$, uniformly in the start vertex $v$ and in the labeling of $G_t$.