The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
From MaRDI portal
Publication:5145259
Recommendations
- Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
- Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
- \((\Delta+1)\) coloring in the congested clique model
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
Cited in
(35)- Near-optimal clustering in the \(k\)-machine model
- Equivalence classes and conditional hardness in massively parallel computations
- Derandomizing local distributed algorithms under bandwidth restrictions
- Streaming and massively parallel algorithms for edge coloring
- Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
- Distributed arboricity-dependent graph coloring via all-to-all communication
- Distributed (+1)-coloring via ultrafast graph shattering
- Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
- scientific article; zbMATH DE number 7758308 (Why is no real title available?)
- Component stability in low-space massively parallel computation
- Maliciously secure massively parallel computation for all-but-one corruptions
- Distributed coloring of hypergraphs
- Distributed Symmetry Breaking on Power Graphs via Sparsification
- Distributed-prover interactive proofs
- The hardness of optimization problems on the weighted massively parallel computation model
- Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
- Graph coloring via degeneracy in streaming and other space-conscious models
- Simple sublinear algorithms for (+1) vertex coloring via asymmetric palette sparsification
- Exponential speedup over locality in \textsf{MPC} with optimal memory
- The distributed complexity of locally checkable labeling problems beyond paths and trees
- Local distributed rounding: generalized to MIS, matching, set cover, and beyond
- Distributed symmetry breaking on power graphs via sparsification
- Massively parallel computation in a heterogeneous regime
- Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model
- Massively parallel algorithms for approximate shortest paths
- Brief announcement: Massively parallel ruling set made deterministic
- Adaptive massively parallel coloring in sparse graphs
- (+1) vertex coloring in O(n) communication
- ( + 1) vertex coloring in O(n) communication
- Parallel derandomization for coloring
- Improved all-pairs approximate shortest paths in congested clique
- Locally computing edge orientations
- Agnostic proper learning of monotone functions: beyond the black-box correction barrier
- Optimal (degree+1)-coloring in congested clique
- A fast coloring oracle for average case hypergraphs
This page was built for publication: The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145259)
