Information retention conjecture for bounded-degree majority dynamics
Information retention conjecture for bounded-degree majority dynamics
Let be a sequence of finite graphs with degrees bounded by and such that
Here, denotes the minimum probability of error when reconstructing the initial common opinion from the limiting opinions, and is the probability that an initial opinion agrees with the underlying signal, with .
Information retention conjecture. For every such sequence and every ,
This conjecture asserts that bounded-degree majority dynamics retains enough information about the initial signal to permit asymptotically error-free reconstruction on every sequence of growing finite graphs. The source provides no resolution, so the conjecture is recorded as open.
Sources & referencesView supporting material
Primary source
Omer Tamuz and Ran J. Tessler, “Majority Dynamics and the Retention of Information”, arXiv:1307.4035 (2014).
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.