Smaller Cuts, Higher Lower Bounds

DOI10.1145/3469834MaRDI QIDQ5035874zbMATH OpenOpenAlexFDO

Authors Amir Abboud, Keren Censor-Hillel, Seri Khoury, Ami Paz

Publication date 22 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.01630

zbMATH Keywords

lower boundsdistributed algorithms

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Quadratic and near-quadratic lower bounds for the CONGEST model
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Hardness of Distributed Optimization
• Distributed minimum cut approximation
• Distributed sparse cut approximation

Cited in

(2)

• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Sharpened lower bounds for cut elimination

This page was built for publication: Smaller Cuts, Higher Lower Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5035874)