Toward Optimal Bounds in the Congested Clique

DOI10.1145/2767386.2767434zbMath1333.68211OpenAlexW1992996565MaRDI QIDQ2796246

Vivek B. Sardeshmukh, Michele Scquizzato, James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju

Publication date: 23 March 2016

Published in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2767386.2767434

zbMATH Keywords

randomizationminimum spanning treegraph connectivitymessage complexitycongested cliquegraph sketches

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (22)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Graph reconstruction in the congested clique ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Lessons from the congested clique applied to MapReduce ⋮ Exact distributed sampling ⋮ Distributed PageRank computation with improved round complexities ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Message lower bounds via efficient network synchronization ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ Unnamed Item ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Near-optimal scheduling in the congested clique ⋮ Approximate minimum directed spanning trees under congestion

Cites Work

• Memorization and Association on a Realistic Neural Model
• Unnamed Item

This page was built for publication: Toward Optimal Bounds in the Congested Clique