Consensus propagation mixing-time conjecture for the m-dimensional torus

Let the graph be the mm-dimensional torus with nn nodes, and let τ\tau^\star denote the mixing time of the directed-edge process associated with consensus propagation. Consensus propagation mixing-time conjecture. For the mm-dimensional torus with nn nodes,

τ=Θ(n(2m1)/m2).\tau^\star = \Theta(n^{(2m-1)/m^2}).

For comparison, the optimized vertex-process mixing time satisfies τ2=Θ(n2/m)\tau_2=\Theta(n^{2/m}); the conjecture predicts the mixing time of consensus propagation and would clarify its advantage over pairwise averaging on higher-dimensional grids. The source presents this as a conjecture without resolving it.

Sources & referencesView supporting material

Primary source

Ciamac C. Moallemi and Benjamin Van Roy, “Consensus Propagation”, arXiv:cs/0603078 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.