Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)

DOI10.1145/3232536zbMath1426.68105OpenAlexW2902899861WikidataQ128875922 ScholiaQ128875922MaRDI QIDQ4625662

Sergei Vassilvitskii, Joshua R. Wang, Tim Roughgarden

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsMapReducemassively parallel computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (6)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Deterministic Massively Parallel Connectivity ⋮ Component stability in low-space massively parallel computation ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ Round Compression for Parallel Matching Algorithms ⋮ Unnamed Item

This page was built for publication: Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)