notesum.ai

Published at December 6

cs.DC

cs.DS

Released Date: December 6, 2024

Authors: Yi-Jun Chang¹, Yanyu Chen¹, Gopinath Mishra¹

Aff.: ¹National University of Singapore

Reference	$b$	Rounds	Total message complexity	Target topology
[dufoulon2024time]	$\Omega(\log^{2}n)$	$O(\log^{5}n)$	$O(n\log^{5}n)$	$O(1)$ -degree expander
Corollary 1.2 (i)	$O(\log^{2}n)$	$O(\log n)$	$O(n\log n)$	Any $O(1)$ -degree graph
Corollary 1.2 (ii)	$O(\log n)$	$O(\log^{2}n)$	$O(n\log^{2}n)$	Any $O(1)$ -degree graph