Quadratic and near-quadratic lower bounds for the CONGEST model

DOI10.4230/LIPICS.DISC.2017.10MaRDI QIDQ6487481zbMATH OpenFDO

Authors Keren Censor-Hillel, Seri Khoury, Ami Paz

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2017.10

zbMATH Keywords

chromatic numberCONGESTlower boundsminimum vertex coverweighted APSP

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Parameterized distributed algorithms
• Approximation of distances and shortest paths in the broadcast congest clique

Cited in

(19)

• Detecting cliques in CONGEST networks
• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed spanner approximation
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Smaller Cuts, Higher Lower Bounds
• Detecting cliques in CONGEST networks
• Distributed Testing of Distance-k Colorings
• Hardness of Distributed Optimization
• Simple and local independent set approximation
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• Improved hardness of approximation of diameter in the CONGEST model
• Improved distributed approximations for maximum independent set
• Distributed maximum matching verification in CONGEST
• Distributed distance approximation
• Approximating bipartite minimum vertex cover in the Congest model
• Connectivity lower bounds in broadcast congested clique
• The message complexity of distributed graph optimization
• Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model
• Distributed fractional local ratio and independent set approximation

This page was built for publication: Quadratic and near-quadratic lower bounds for the CONGEST model

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