Component stability in low-space massively parallel computation
From MaRDI portal
Publication:6126138
DOI10.1007/s00446-024-00461-9OpenAlexW3166172671WikidataQ128337881 ScholiaQ128337881MaRDI QIDQ6126138
Peter Davies-Peck, Merav Parter, Artur Czumaj
Publication date: 9 April 2024
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-024-00461-9
Cites Work
- Unnamed Item
- Unnamed Item
- On the computational complexity of MapReduce
- Equivalence classes and conditional hardness in massively parallel computations
- Distributed coloring algorithms for triangle-free graphs
- Pseudorandomness
- Sorting, Searching, and Simulation in the MapReduce Framework
- The price of being near-sighted
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Locality in Distributed Graph Algorithms
- Simple Constructions of Almost k-wise Independent Random Variables
- An Improved Distributed Algorithm for Maximal Independent Set
- Distributed Degree Splitting, Edge Coloring, and Orientations
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- Communication Steps for Parallel Query Processing
- What Can be Computed Locally?
- Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
- Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
- Round Compression for Parallel Matching Algorithms
- Some simple distributed algorithms for sparse networks
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- On the Use of Randomness in Local Distributed Graph Algorithms
- The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
- Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
- Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
- Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
- Parallel algorithms for geometric graph problems
- A lower bound for the distributed Lovász local lemma
- Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
- Distributed algorithms for the Lovász local lemma and graph coloring
- Almost \(k\)-wise independent sample spaces and their cryptologic applications
This page was built for publication: Component stability in low-space massively parallel computation
