- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
- Dark green border
- this is in Mathlib
\(x_{t+1}(v)=\frac1{\deg v}\sum _{u\sim v}x_t(u)\), and \(\bar x=\sum _v\deg (v)\, x_0(v)/\sum _v\deg (v)\).
\(G\) is \(d\)-regular on two clusters \(V_1,V_2\) of \(n\) nodes, each node having \(b\) neighbours in the other cluster; \(\chi =\mathbb 1_{V_1}-\mathbb 1_{V_2}\), \(P=A/d\) with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \), \(\lambda =\max _{i\ge 3}|\lambda _i|\). Node \(v\) is blue at round \(t\) if \(x_t(v)\ge x_{t-1}(v)\); a coloring is a strong reconstruction if no color appears in both clusters. \(T(n,\delta )=\lceil \log (4n^3)/\log (1+\delta )\rceil +1\).
A step on the edge \((i,j)\) multiplies the state by \(W_{ij}=I-\frac12(e_i-e_j)(e_i-e_j)^\top \); a run applies the steps of a list of oriented edges in order. For a stochastic matrix \(P\) (given as a kernel), \(\bar W_P=I-\bar D/2n+(P+P^\top )/2n\) with \(\bar D_{ii}=\sum _j(P_{ij}+P_{ji})\), and \(\bar W=I-L/2m\) with \(L\) the Laplacian.
One uniformly random edge is activated per round; a node activated for the first time draws a uniform sign, and both endpoints take the average of their two values. The rounds are i.i.d. uniform darts of \(G\).
\(G\) is \(d\)-regular with communities \(V_1\) and \(V_2=V_1^c\) of size \(n/2\), each node having \(b\) neighbours in the other community, \(0{\lt}b\), \(2b{\lt}d{\lt}n\). The state splits as \(x=x_\parallel +y+z\) along \(\mathbb 1\), \(\chi =\mathbb 1_{V_1}-\mathbb 1_{V_2}\) and their orthogonal complement; \(\lambda _2=2b/d\), and \(\lambda _3\) enters as a lower bound on the Rayleigh quotient of \(L/d\) on the complement.
\(P=D^{-1}A\) is the transition matrix of the random walk, \(N=D^{-1/2}AD^{-1/2}\) its symmetric version with eigenvalues \(\lambda _1\ge \lambda _2\ge \dots \ge \lambda _n\), \(\lambda =\max \{ |\lambda _2|,|\lambda _n|\} \) (\(0\) if \(n{\lt}2\)), and \(\pi (v)=\deg (v)/2m\) with \(m\) the number of edges.
For uniform \(x\in \{ \pm 1\} ^{2n}\), \(P(\langle x,\chi \rangle =0)=\binom {2n}{n}/4^n\le 1/\sqrt{\pi n}\).
\(\sum _v\deg (v)\, x_{t}(v)\) does not depend on \(t\); without isolated nodes, a round never leaves an interval containing all current values.
If \(\lambda {\lt}1-2b/d\) and \(x\in \{ \pm 1\} ^{2n}\), then \(|x_t(v)-\alpha _1-\alpha _2(1-2b/d)^t\chi (v)|\le \lambda ^t\sqrt{2n}\) with \(\alpha _1=\langle x,\mathbb 1\rangle /2n\), \(\alpha _2=\langle x,\chi \rangle /2n\).
\(W_{ij}x\) replaces \(x_i\) and \(x_j\) by their average and keeps the other values; \(W_{ij}\) is doubly stochastic and a symmetric projection, \(W_{ij}^\top W_{ij}=W_{ij}\).
A uniform dart is a uniform edge; a node holds a value exactly when it has been activated, and the protocol’s values are those of the averaging process started from the coins \(\sigma \); the sum of the values is conserved.
With \(\beta =\langle x,\chi \rangle /n\): \(\mathbb E\| z'\| ^2\le (1-\lambda _3/n)\| z\| ^2+\lambda _2\beta ^2\) and, for every \(\gamma \), \(\mathbb E\, n(\beta '-\gamma )^2\le (1-\lambda _2/n)\, n(\beta -\gamma )^2+\lambda _2\gamma ^2 +(4\lambda _2/n^2)(n\beta ^2+\| z\| ^2)\).
\(P^t(u,v)=W_t(u,v)\) is the probability that the walk from \(u\) is at \(v\) after \(t\) steps, and \(x_t=P^tx_0\). If every degree is positive, \(P\) and \(N\) have the same characteristic polynomial, so \(\lambda \) is computed from the spectrum of \(P\).
\(x_t(v)=\sum _u W_t(v,u)\, x_0(u)\) with \(W_t\) stochastic and \(W_t(v,u){\gt}0\) when a walk of length \(t\) joins \(v\) and \(u\). On a connected graph with an odd closed walk, some length \(L\) joins every pair.
On a connected graph with an odd closed walk, \(x_t(v)\to \bar x\) for every \(v\).
On a connected clustered graph with \(1-2b/d{\gt}(1+\delta )\lambda \), if \(x\in \{ \pm 1\} ^{2n}\) and \(\langle x,\chi \rangle \ne 0\), then for \(t\ge T(n,\delta )=O(\log n/\delta )\), \(\operatorname {sgn}(x_{t-1}(u)-x_t(u))=\operatorname {sgn}(\langle x,\chi \rangle \chi (u))\).
If a uniformly random node \(i\) contacts \(j\) with probability \(P_{ij}\), then \(\mathbb E[W_{ij}]=\bar W_P\); if a uniformly random oriented edge is selected, then \(\mathbb E[W_{ij}]=\bar W\). On a \(d\)-regular graph with \(d{\gt}0\) and \(P=D^{-1}A\) both equal \((1-1/n)I+P/n\).
For a uniformly random oriented edge, \(\mathbb E[W^\top W]=\bar W\) and \(\mathbb E\| Wx\| ^2=x^\top \bar Wx\); after \(t\) independent uniformly random oriented edges, \(\mathbb E[x_t]=\bar W^tx_0\).
\(\bar W\chi =(1-\lambda _2/n)\chi \), the expected state decomposes exactly as in Lemma B.1, and the monotonicity and sign criteria of Lemmas B.3 and B.4 hold at every node.
If \(100\lambda _2\log n\le \lambda _3\) and \(3(n/\lambda _3)\log n\le t\le n/(4\lambda _2)\), then \(\mathbb E\| y^{(t)}+z^{(t)}-y^{(0)}\| ^2\le 3\lambda _2t/n\).
If \(\lambda _2/\lambda _3\le \lambda _3\varepsilon ^4/(c\log ^2n)\), then with probability at least \(1-\varepsilon \) at least \((1-3\varepsilon )n\) nodes are \(\varepsilon \)-good at every round of the phase \(6(n/\lambda _3)\log n\le t\le 12(n/\lambda _3)\log n\).
\(W_t\) is a symmetric projection, \(\mathbb E[W]=\bar W=I-L/2m\) is symmetric and doubly stochastic, \(\mathbb E[x^{(t)}]=\bar W^tx^{(0)}\) and \(\mathbb E\| Wx\| ^2=x^\top \bar Wx\).
- Averaging.Opportunistic.stepMatrix
- Averaging.Opportunistic.meanStepMatrix
- Averaging.Opportunistic.stepMatrix_mulVec
- Averaging.Opportunistic.stepMatrix_isSymm
- Averaging.Opportunistic.stepMatrix_mul_self
- Averaging.Opportunistic.avg_stepMatrix
- Averaging.Opportunistic.meanStepMatrix_isSymm
- Averaging.Opportunistic.meanStepMatrix_mem_doublyStochastic
- Averaging.Opportunistic.avg_edgeAvg
- Averaging.Opportunistic.expList_avgRun
- Averaging.Opportunistic.avg_sum_sq_edgeAvg
Under the hypothesis of Lemma 4.2, with probability at least \(1-4\varepsilon \) at least \((1-4\varepsilon )n\) nodes have the sign of their community’s initial average throughout the phase, and with probability at least \(1/2-6\varepsilon \) the signs of the values are a \(6\varepsilon \)-weak reconstruction at every round of the phase.
- Averaging.Opportunistic.IsWeakReconstruction
- Averaging.Opportunistic.IsClusteredRegular.avg_abs_blockSum_le_mul
- Averaging.Opportunistic.IsClusteredRegular.avg_blockSum_mul_neg
- Averaging.Opportunistic.IsClusteredRegular.prob_sign_window
- Averaging.Opportunistic.IsClusteredRegular.prob_weakReconstruction_window
- Averaging.Opportunistic.sign_phase
- Averaging.Opportunistic.weakReconstruction_phase