Christoph Grunau

I am currently a postdoctoral scholar at ETH Zurich, working in the research group of Rasmus Kyng.

I completed my Ph.D. in December 2024 at ETH Zurich, where I had the pleasure of being advised by Mohsen Ghaffari. My dissertation, titled Sampling with Certainty in Distributed and Parallel Computations, was recognized with the EATCS Distinguished Dissertation Award 2025 and the ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award 2025.

From February 2023 to February 2024, I was a visiting researcher at MIT.

My research interests lie in theoretical computer science, with a focus on distributed algorithms, parallel algorithms, and clustering algorithms.

If you wish to contact me, please use my email cgrunau at inf.ethz.ch.

Teaching

Publications (The author ordering is alphabetical (,) or random (®))
(Google Scholar)

• Mohsen Ghaffari, Christoph Grunau: Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
  IEEE Symposium on Foundations of Computer Science (FOCS) 2025;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau: Density-Dependent Graph Orientation and Coloring in Scalable MPC
  Principles of Distributed Computing (PODC) 2025;
  
• Mohsen Ghaffari, Christoph Grunau: Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
  IEEE Symposium on Foundations of Computer Science (FOCS) 2024;
  Best Paper Award at FOCS'24
  [arXiv]
• Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin Hao Su: Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
  European Symposium on Algorithms (ESA) 2024;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau: Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
  ACM Symposium on Theory of Computing (STOC) 2024;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau: Dynamic O(arboricity) coloring in polylogarithmic worst-case time
  ACM Symposium on Theory of Computing (STOC) 2024;
  [arXiv]
• Jakub Łącki ® Bernhard Haeupler ® Christoph Grunau ® Václav Rozhoň ® Rajesh Jayaram: Fully Dynamic Consistent k-Center Clustering
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024;
  [arXiv]
• Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, Jara Uitto: Conditionally Optimal Parallel Coloring of Forests
  International Symposium on DIStributed Computing (DISC) 2023;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň: Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
  IEEE Symposium on Foundations of Computer Science (FOCS) 2023;
  [arXiv]
• Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň: Noisy k-means++ revisited
  European Symposium on Algorithms (ESA) 2023;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau, Jiahao Qu: Nearly Work-Efficient Parallel DFS in Undirected Graphs
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2023;
  Best Paper Award at SPAA'23
  [arXiv]
• Manuela Fischer, Jeff Giliberti, Christoph Grunau: Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2023;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau: Faster Deterministic Distributed MIS and Approximate Matching
  ACM Symposium on Theory of Computing (STOC) 2023;
  [arXiv]
• Václav Rozhoň ® Bernhard Haeupler ® Anders Martinsson ® Christoph Grunau ® Goran Zuzic: Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
  ACM Symposium on Theory of Computing (STOC) 2023;
  [arXiv]
• Václav Rozhoň ® Bernhard Haeupler ® Christoph Grunau: A Simple Deterministic Distributed Low-Diameter Clustering
  ACM-SIAM Symposium on Simplicity in Algorithms (SOSA) 2023;
  
• Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhoň: Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023;
  [arXiv]
• Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, Václav Rozhoň: Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023;
  [arXiv]
• Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň, Jakub Tětek: A Nearly Tight Analysis of Greedy k-means++
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023;
  [arXiv]
• Manuela Fischer, Jeff Giliberti, Christoph Grunau: Improved Deterministic Connectivity in Massively Parallel Computation
  International Symposium on DIStributed Computing (DISC) 2022;
  [arXiv]
• Michael Elkin ® Bernhard Haeupler ® Václav Rozhoň ® Christoph Grunau: Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
  IEEE Symposium on Foundations of Computer Science (FOCS) 2022;
  [arXiv]
• Christoph Grunau, Václav Rozhoň: Adapting k-means Algorithms for Outliers
  International Conference on Machine Learning (ICML) 2022;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau, and Slobodan Mitrovic : Massively Parallel Algorithms for b-Matching
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2022;
  
• Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhoň : Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
  ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2022;
  [arXiv]
• Christoph Grunau ® Václav Rozhoň ® Sebastian Brandt : The Landscape of Distributed Complexities on Trees and Beyond
  Principles of Distributed Computing (PODC) 2022;
  [arXiv]
• Václav Rozhoň ® Christoph Grunau ® Bernhard Haeupler ® Goran Zuzic ® Jason Li: Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms
  ACM Symposium on Theory of Computing (STOC) 2022;
  [arXiv]
• Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, Zoltán Vidnyánszky: Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
  Innovations of Theoretical Computer Science (ITCS) 2022;
  [arXiv]
• Sebastian Brandt, Christoph Grunau, Václav Rozhoň: The Randomized Local Computation Complexity of the Lovász Local Lemma
  Principles of Distributed Computing (PODC) 2021;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň: Improved Deterministic Network Decomposition
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021;
  [arXiv]
• Mohsen Ghaffari, Christoph Grunau, Ce Jin: Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
  International Symposium on DIStributed Computing (DISC) 2020;
  [arXiv]
• Sebastian Brandt, Christoph Grunau, Václav Rozhoň: Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
  Principles of Distributed Computing (PODC) 2020;
  [arXiv]
• Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhoň: k-means++: few more steps yield constant approximation
  International Conference on Machine Learning (ICML) 2020;
  [arXiv]
• Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, Ali Vakilian: Improved Local Computation Algorithm for Set Cover via Sparsification
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020;
  [arXiv],