Mohsen Ghaffari

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates

2022 · arXiv (Cornell University)

This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification: We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in $\textrm{polylog}(n)$ rounds in weighted …

Faster Deterministic Distributed MIS and Approximate Matching

2023 · Repository for Publications and Research Data (ETH Zurich)

$ \renewcommand{\tilde}{\widetilde} $We present an $\tilde{O}(\log^2 n)$ round deterministic distributed algorithm for the maximal independent set problem. By known reductions, this round complexity extends also to maximal matching, $Δ+1$ vertex coloring, and $2Δ-1$ edge coloring. …

Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping

2023 · arXiv (Cornell University)

We present an efficient parallel derandomization method for randomized algorithms that rely on concentrations such as the Chernoff bound. This settles a classic problem in parallel derandomization, which dates back to the 1980s. Consider the …