Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions

Yi-Jun Chang, Hsin-Hao Su

Many combinatorial optimization problems can be approximated within $(1\pm \hat{I}\mu )$ factors in $\text{poly}(\log n,1/\hat{I}\mu )$ rounds in the LOCAL model via network decompositions [Ghaffa…