Constraint graph powering with local-view labels

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.