Plurality decoding of powered local views

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$.