Deterministic Massively Parallel Connectivity (Q6069413)

scientific article; zbMATH DE number 7764826

Language	Label	Description	Also known as
English	Deterministic Massively Parallel Connectivity	scientific article; zbMATH DE number 7764826

Statements

instance of

scholarly article

0 references

title

Deterministic Massively Parallel Connectivity (English)

0 references

Deterministic massively parallel connectivity (English)

0 references

0 references

0 references

SIAM Journal on Computing

0 references

Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

0 references

publication date

14 November 2023

0 references

8 December 2023

0 references

full work available at URL

https://arxiv.org/abs/2108.04102

0 references

zbMATH Keywords

derandomization

0 references

connectivity

0 references

MapReduce

0 references

MPC

0 references

massively parallel algorithms

0 references

mapreduce

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

0 references

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

Simple Constructions of Almost k-wise Independent Random Variables

0 references

Almost \(k\)-wise independence versus \(k\)-wise independence

0 references

Parallel algorithms for geometric graph problems

0 references

Q2798999

0 references

Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs

0 references

Parallel approximate undirected shortest paths via low hop emulators

0 references

Massively Parallel Computation of Matching and MIS in Sparse Graphs

0 references

Brief Announcement: MapReduce Algorithms for Massive Trees

0 references

Efficient Deterministic Distributed Coloring with Small Bandwidth

0 references

Communication Steps for Parallel Query Processing

0 references

Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space

0 references

Simple, Deterministic, Constant-Round Coloring in the Congested Clique

0 references

The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

0 references

On the power of two-point based sampling

0 references

Approximation algorithms for metric facility location and <i>k</i> -Median problems using the primal-dual schema and Lagrangian relaxation

0 references

Fast Distributed Approximations in Planar Graphs

0 references

Round compression for parallel matching algorithms

0 references

Derandomizing local distributed algorithms under bandwidth restrictions

0 references

Improved algorithms via approximations of probability distributions

0 references

Universal classes of hash functions

0 references

Deterministic Distributed Dominating Set Approximation in the CONGEST Model

0 references

Efficient approximation of product distributions

0 references

On a combinatorial game

0 references

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

0 references

Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set

0 references

Sorting, Searching, and Simulation in the MapReduce Framework

0 references

Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation

0 references

Lessons from the congested clique applied to MapReduce

0 references

Q4608063

0 references

Almost \(k\)-wise independent sample spaces and their cryptologic applications

0 references

Q5417679

0 references

Walking randomly, massively, and efficiently

0 references

A Simple Parallel Algorithm for the Maximal Independent Set Problem

0 references

Removing randomness in parallel computation without a processor penalty

0 references

Q3413301

0 references

Leveraging Linial’s Locality Limit

0 references

The probabilistic method yields deterministic parallel algorithms

0 references

Q4856179

0 references

Small-Bias Probability Spaces: Efficient Constructions and Applications

0 references

A deterministic algorithm for the MST problem in constant rounds of congested clique

0 references

Equivalence classes and conditional hardness in massively parallel computations

0 references

Probabilistic construction of deterministic algorithms: approximating packing integer programs

0 references

Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)

0 references

Chernoff–Hoeffding Bounds for Applications with Limited Independence

0 references

Derandomizing local distributed algorithms under bandwidth restrictions

0 references

Identifiers

0 references

0 references

10.1145/3519935.3520055

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6069413