Equivalence classes and conditional hardness in massively parallel computations
DOI10.1007/s00446-021-00418-2zbMath1483.68032arXiv2001.02191OpenAlexW3000033813MaRDI QIDQ2121067
Danupon Nanongkai, Michele Scquizzato
Publication date: 1 April 2022
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2001.02191
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Log-space algorithms for paths and matchings in \(k\)-trees
- Lessons from the congested clique applied to MapReduce
- Symmetric space-bounded computation
- Space-bounded reducibility among combinatorial problems
- Counting quantifiers, successor relations, and logarithmic space
- On the computational complexity of MapReduce
- The complexity of planarity testing
- Circuits, matrices, and nonassociative computation
- Relationships between nondeterministic and deterministic tape complexities
- Toward Optimal Bounds in the Congested Clique
- On the Complexity of List Ranking in the Parallel External Memory Model
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- On the power of the congested clique model
- Sorting, Searching, and Simulation in the MapReduce Framework
- Constant Depth Reducibility
- Undirected connectivity in log-space
- A taxonomy of problems with fast parallel algorithms
- Problems complete for deterministic logarithmic space
- Two Applications of Inductive Counting for Complementation Problems
- New problems complete for nondeterministic log space
- Communication-Efficient Parallel Sorting
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- Communication Steps for Parallel Query Processing
- Efficient massively parallel methods for dynamic programming
- Brief Announcement: MapReduce Algorithms for Massive Trees
- Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- Round Compression for Parallel Matching Algorithms
- Walking randomly, massively, and efficiently
- Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
- The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
- Massively Parallel Computation of Matching and MIS in Sparse Graphs
- Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
- Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
- Sublinear Algorithms for (Δ + 1) Vertex Coloring
- 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
- Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence
- Parallel algorithms for geometric graph problems
- Computational Complexity
- Distributed Computation of Large-scale Graph Problems
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Massively Parallel Algorithms for Minimum Cut
- Equivalence classes and conditional hardness in massively parallel computations
- A compendium of problems complete for symmetric logarithmic space
This page was built for publication: Equivalence classes and conditional hardness in massively parallel computations
