Christoph Grunau
3 papers in the PaperMetrix corpus
Papers by this author
-
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 …