On the power of the congested clique model

DOI10.1145/2611462.2611493zbMath1321.68381OpenAlexW2107805020MaRDI QIDQ2943637

Rotem Oshman, Andrew Drucker, Fabian Kuhn

Publication date: 3 September 2015

Published in: Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/19437208/Drucker_Kuhn_ET_AL_2014_On_the_Power_of_the_Congested_Clique_Model.pdf

zbMATH Keywords

lower boundscongested cliquesubgraph detection

Mathematics Subject Classification ID

Related Items (44)

Equivalence classes and conditional hardness in massively parallel computations ⋮ The Range of Topological Effects on Communication ⋮ Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Graph reconstruction in the congested clique ⋮ Distributed Testing of Distance-k Colorings ⋮ Unnamed Item ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ A note on improved results for one round distributed clique listing ⋮ Lessons from the congested clique applied to MapReduce ⋮ Fault-tolerant graph realizations in the congested clique ⋮ On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model ⋮ On the power of threshold-based algorithms for detecting cycles in the CONGEST model ⋮ Energy-efficient distributed algorithms for synchronous networks ⋮ Unnamed Item ⋮ Distributed PageRank computation with improved round complexities ⋮ Brief Announcement: What Can We Compute in a Single Round of the Congested Clique? ⋮ Detecting cliques in CONGEST networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Algebraic methods in the congested clique ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Unnamed Item ⋮ Sparse matrix multiplication and triangle listing in the congested clique model ⋮ Message lower bounds via efficient network synchronization ⋮ The role of randomness in the broadcast congested clique model ⋮ Sub-logarithmic distributed algorithms for metric facility location ⋮ The Impact of Locality in the Broadcast Congested Clique Model ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Fast approximate shortest paths in the congested clique ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Distributed Spanner Approximation ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Approximate minimum directed spanning trees under congestion

This page was built for publication: On the power of the congested clique model