On the power of the congested clique model

DOI10.1145/2611462.2611493zbMath1321.68381MaRDI 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 bounds; congested clique; subgraph detection

Mathematics Subject Classification ID

91A43: Games involving graphs

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68R10: Graph theory (including graph drawing) in computer science

94A12: Signal theory (characterization, reconstruction, filtering, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68M12: Network protocols

68W15: Distributed algorithms

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Distributed Spanner Approximation, Distributed Testing of Distance-k Colorings, The Impact of Locality in the Broadcast Congested Clique Model, Distributed construction of purely additive spanners, Fast distributed algorithms for testing graph properties, The Communication Complexity of Set Intersection and Multiple Equality Testing, Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE, Sub-logarithmic distributed algorithms for metric facility location, Lessons from the congested clique applied to MapReduce, Algebraic methods in the congested clique, The role of randomness in the broadcast congested clique model, Near-optimal clustering in the \(k\)-machine model, Fast approximate shortest paths in the congested clique, Approximate minimum directed spanning trees under congestion, Equivalence classes and conditional hardness in massively parallel computations, Sublinear-time distributed algorithms for detecting small cliques and even cycles, Graph reconstruction in the congested clique, Derandomizing local distributed algorithms under bandwidth restrictions, Detecting cliques in CONGEST networks, Fooling views: a new lower bound technique for distributed computations under congestion, Sparse matrix multiplication and triangle listing in the congested clique model, Message lower bounds via efficient network synchronization, Proof-labeling schemes: broadcast, unicast and in between, A note on improved results for one round distributed clique listing, The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model, Message Lower Bounds via Efficient Network Synchronization, Sparsifying Congested Cliques and Core-Periphery Networks, The Range of Topological Effects on Communication, 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