Equivalence classes and conditional hardness in massively parallel computations (Q2121067): Difference between revisions

@@ Property / describes a project that uses @@
+Hadoop
@@ Property / describes a project that uses: Hadoop / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+Dryad
@@ Property / describes a project that uses: Dryad / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3000033813
@@ Property / OpenAlex ID: W3000033813 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.02191
@@ Property / arXiv ID: 2001.02191 / rank @@
+Normal rank
@@ Property / cites work @@
+Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
+Normal rank
@@ Property / cites work @@
+Q5743413
@@ Property / cites work: Q5743413 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of planarity testing
@@ Property / cites work: The complexity of planarity testing / rank @@
+Normal rank
@@ Property / cites work @@
+A compendium of problems complete for symmetric logarithmic space
+Normal rank
@@ Property / cites work @@
+Parallel algorithms for geometric graph problems
@@ Property / cites work: Parallel algorithms for geometric graph problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3119175
@@ Property / cites work: Q3119175 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5091162
@@ Property / cites work: Q5091162 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
+Normal rank
@@ Property / cites work @@
+Sublinear Algorithms for (Δ + 1) Vertex Coloring
@@ Property / cites work: Sublinear Algorithms for (Δ + 1) Vertex Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Q4608050
@@ Property / cites work: Q4608050 / rank @@
+Normal rank
@@ Property / cites work @@
+Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Communication Steps for Parallel Query Processing
@@ Property / cites work: Communication Steps for Parallel Query Processing / rank @@
+Normal rank
@@ Property / cites work @@
+Circuits, matrices, and nonassociative computation
+Normal rank
@@ Property / cites work @@
+Massively Parallel Computation of Matching and MIS in Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Brief Announcement: MapReduce Algorithms for Massive Trees
+Normal rank
@@ Property / cites work @@
+Two Applications of Inductive Counting for Complementation Problems
+Normal rank
@@ Property / cites work @@
+Q4607964
@@ Property / cites work: Q4607964 / rank @@
+Normal rank
@@ Property / cites work @@
+Constant Depth Reducibility
@@ Property / cites work: Constant Depth Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
+Normal rank
@@ Property / cites work @@
+A taxonomy of problems with fast parallel algorithms
+Normal rank
@@ Property / cites work @@
+Problems complete for deterministic logarithmic space
+Normal rank
@@ Property / cites work @@
+Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
+Normal rank
@@ Property / cites work @@
+Round Compression for Parallel Matching Algorithms
+Normal rank
@@ Property / cites work @@
+Log-space algorithms for paths and matchings in \(k\)-trees
+Normal rank
@@ Property / cites work @@
+Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
+Normal rank
@@ Property / cites work @@
+On the power of the congested clique model
@@ Property / cites work: On the power of the congested clique model / rank @@
+Normal rank
@@ Property / cites work @@
+Counting quantifiers, successor relations, and logarithmic space
+Normal rank
@@ Property / cites work @@
+On the computational complexity of MapReduce
@@ Property / cites work: On the computational complexity of MapReduce / rank @@
+Normal rank
@@ Property / cites work @@
+Q5875618
@@ Property / cites work: Q5875618 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
+Normal rank
@@ Property / cites work @@
+Massively Parallel Algorithms for Minimum Cut
@@ Property / cites work: Massively Parallel Algorithms for Minimum Cut / rank @@
+Normal rank
@@ Property / cites work @@
+Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
+Normal rank
@@ Property / cites work @@
+Communication-Efficient Parallel Sorting
@@ Property / cites work: Communication-Efficient Parallel Sorting / rank @@
+Normal rank
@@ Property / cites work @@
+Sorting, Searching, and Simulation in the MapReduce Framework
+Normal rank
@@ Property / cites work @@
+Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence
+Normal rank
@@ Property / cites work @@
+Toward Optimal Bounds in the Congested Clique
@@ Property / cites work: Toward Optimal Bounds in the Congested Clique / rank @@
+Normal rank
@@ Property / cites work @@
+Lessons from the congested clique applied to MapReduce
+Normal rank
@@ Property / cites work @@
+Efficient massively parallel methods for dynamic programming
+Normal rank
@@ Property / cites work @@
+Q4227581
@@ Property / cites work: Q4227581 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Complexity of List Ranking in the Parallel External Memory Model
+Normal rank
@@ Property / cites work @@
+Space-bounded reducibility among combinatorial problems
+Normal rank
@@ Property / cites work @@
+New problems complete for nondeterministic log space
+Normal rank
@@ Property / cites work @@
+Q3140397
@@ Property / cites work: Q3140397 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5417679
@@ Property / cites work: Q5417679 / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Computation of Large-scale Graph Problems
+Normal rank
@@ Property / cites work @@
+Walking randomly, massively, and efficiently
@@ Property / cites work: Walking randomly, massively, and efficiently / rank @@
+Normal rank
@@ Property / cites work @@
+Symmetric space-bounded computation
@@ Property / cites work: Symmetric space-bounded computation / rank @@
+Normal rank
@@ Property / cites work @@
+Equivalence classes and conditional hardness in massively parallel computations
+Normal rank
@@ Property / cites work @@
+Q4234059
@@ Property / cites work: Q4234059 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+Undirected connectivity in log-space
@@ Property / cites work: Undirected connectivity in log-space / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom walks on regular digraphs and the RL vs. L problem
+Normal rank
@@ Property / cites work @@
+Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
+Normal rank
@@ Property / cites work @@
+Relationships between nondeterministic and deterministic tape complexities
+Normal rank
@@ Property / cites work @@
+Q2965522
@@ Property / cites work: Q2965522 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3392273
@@ Property / cites work: Q3392273 / rank @@
+Normal rank
@@ Property / cites work @@
+ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
+Normal rank
@@ Property / cites work @@
+Subcubic Equivalences Between Path, Matrix, and Triangle Problems
+Normal rank