Deterministic Massively Parallel Connectivity
From MaRDI portal
Publication:6069413
DOI10.1137/22m1520177arXiv2108.04102MaRDI QIDQ6069413
Publication date: 14 November 2023
Published in: SIAM Journal on Computing, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2108.04102
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Theory of computing (68Qxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lessons from the congested clique applied to MapReduce
- Almost \(k\)-wise independence versus \(k\)-wise independence
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- On the power of two-point based sampling
- Universal classes of hash functions
- Removing randomness in parallel computation without a processor penalty
- The probabilistic method yields deterministic parallel algorithms
- Improved algorithms via approximations of probability distributions
- Derandomizing local distributed algorithms under bandwidth restrictions
- Sorting, Searching, and Simulation in the MapReduce Framework
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Simple Constructions of Almost k-wise Independent Random Variables
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- Communication Steps for Parallel Query Processing
- Efficient approximation of product distributions
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Brief Announcement: MapReduce Algorithms for Massive Trees
- Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
- Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
- Parallel approximate undirected shortest paths via low hop emulators
- Walking randomly, massively, and efficiently
- Deterministic Distributed Dominating Set Approximation in the CONGEST Model
- 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
- Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
- Round compression for parallel matching algorithms
- 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
- Efficient Deterministic Distributed Coloring with Small Bandwidth
- Simple, Deterministic, Constant-Round Coloring in the Congested Clique
- Equivalence classes and conditional hardness in massively parallel computations
- On a combinatorial game
- Almost \(k\)-wise independent sample spaces and their cryptologic applications
- A deterministic algorithm for the MST problem in constant rounds of congested clique
This page was built for publication: Deterministic Massively Parallel Connectivity
