5 citations · 8 across the 9 of their papers we have counts for
15 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…
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…
Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari, Christoph Grunau
We present an round deterministic distributed algorithm for the maximal independent set problem. By known reductions, thi…