Smaller Cuts, Higher Lower Bounds

DOI10.1145/3469834OpenAlexW3204294665MaRDI QIDQ5035874FDOQ5035874

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

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

zbMATH Keywords

lower boundsdistributed algorithms

Mathematics Subject Classification ID

Computer science (68-XX)

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)