Consensus propagation mixing-time conjecture for the m-dimensional torus
Consensus propagation mixing-time conjecture for the m-dimensional torus
Let the graph be the -dimensional torus with nodes, and let denote the mixing time of the directed-edge process associated with consensus propagation. Consensus propagation mixing-time conjecture. For the -dimensional torus with nodes,
For comparison, the optimized vertex-process mixing time satisfies ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.