Reaching a Consensus on Random Networks: The Power of Few

by Linh Tran and Van Vu

Theory of Computing, Volume 19(6), pp. 1-21, 2023

Bibliography with links to cited articles

[1]   Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest: Time-space trade-offs in population protocols. In Proc. 28th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’17), pp. 2560–2579. SIAM, 2017. [doi:10.1137/1.9781611974782.169, arXiv:1602.08032]

[2]   Dan Alistarh, Rati Gelashvili, and Milan Vojnović: Fast and exact majority in population protocols. In Proc. ACM Symp. Principles Distrib. Computing (PODC’15), pp. 47–56. ACM Press, 2015. [doi:10.1145/2767386.2767429]

[3]   Itai Benjamini, Siu-On Chan, Ryan O’Donnell, Omer Tamuz, and Li-Yang Tan: Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. Stoch. Proc. Appl., 126(9):2719–2733, 2016. [doi:10.1016/]

[4]   Béla Bollobás: Models of random graphs. In Random Graphs, chapter 2, pp. 34–50. Cambridge Univ. Press, 2001. [doi:10.1017/CBO9780511814068.004]

[5]   Peter Clifford and Aidan Sudbury: A model for spatial conflict. Biometrika, 60(3):581–588, 1973. [doi:10.1093/biomet/60.3.581]

[6]   Morris H. DeGroot: Reaching a consensus. J. Amer. Statistical Assoc., 69(345):118–121, 1974. [doi:10.2307/2285509]

[7]   Carl-Gustav Esseen: A moment inequality with an application to the central limit theorem. Scandinavian Actuarial J., 1956(2):160–170, 1956. [doi:10.1080/03461238.1956.10414946]

[8]   Nikolaos Fountoulakis, Mihyun Kang, and Tamás Makai: Resolution of a conjecture on majority dynamics: Rapid stabilisation in dense random graphs. Random Struct. Algor., 57(4):1134–1156, 2020. [doi:10.1002/rsa.20970, arXiv:1910.05820]

[9]   Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statistical Assoc., 58(301):13–30, 1963. [doi:10.1080/01621459.1963.10500830]

[10]   Svante Janson, Tomasz Łuczak, and Andrzej Rucinski: Random Graphs. Wiley, 2011. Chapter 1 (Preliminaries), pages 1–23. [doi:10.1002/9781118032718.ch1]

[11]   Jiři Matoušek and Jaroslav Nešetřil: Invitation to Discrete Mathematics. Oxford Univ. Press, 1998. LINK.

[12]   Elchanan Mossel, Joe Neeman, and Omer Tamuz: Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3):408–429, 2014. [doi:10.1007/s10458-013-9230-4]

[13]   Elchanan Mossel and Omer Tamuz: Opinion exchange dynamics. Probability Surveys, 14:155–204, 2017. [doi:10.1214/14-PS230]

[14]   Ashwin Sah and Mehtaab Sawhney: Majority dynamics: The power of one, 2021. [arXiv:2105.13301]

[15]   Irina Gennad’evna Shevtsova: An improvement of convergence rate estimates in the Lyapunov theorem. Doklady Math., 82(3):862–864, 2010. [doi:10.1134/S1064562410060062]

[16]   Linh Tran and Van Vu: Reaching a consensus on random networks: The power of few. In Proc. 24th Internat. Conf. on Randomization and Computation (RANDOM’20), pp. 20:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.APPROX/RANDOM.2020.20]

[17]   Linh Tran and Van Vu: The “power of few” phenomenon: The sparse case, 2023. [arXiv:2302.05605]

[18]   Roman Vershynin: Concentration of sums of independent random variables. In High-Dimensional Probability: An Introduction with Applications in Data Science, chapter 2, pp. 11–37. Cambridge Univ. Press, 2018. [doi:10.1017/9781108231596.005]