5 citations · 25 across the 19 of their papers we have counts for
8 papers · 1 filter
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari, Christoph Grunau
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…
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
We present a novel technique for work-efficient parallel derandomization, for algorithms that rely on the concentration of measure bounds such as Chernoff, Hoeffding, and Bernstein…
Conditionally Optimal Parallel Coloring of Forests
Christoph Grunau, Rustam Latypov, Yannic Maus +2
We show the first conditionally optimal deterministic algorithm for -coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in $O(\log…
Fully Dynamic Consistent -Center Clustering
Jakub Łącki, Bernhard Haeupler, Christoph Grunau +2
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate -center solution during a sequence of point inser…
Noisy k-means++ Revisited
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň
The -means++ algorithm by Arthur and Vassilvitskii [SODA 2007] is a classical and time-tested algorithm for the -means problem. While being very practical, the algorithm also…
Nearly Work-Efficient Parallel DFS in Undirected Graphs
Mohsen Ghaffari, Christoph Grunau, Jiahao Qu
We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any -node -edge undirected grap…