Papers
This page lists my papers. It is less updated than my Google Scholar page, but it sometimes additionally links some relevant slides / talk recordings / …
-
Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert Tarjan, Jakub Tětek:
Bidirectional Dijkstra’s Algorithm is Instance-Optimal
ACM-SIAM Symposium on Simplicity in Algorithms (SOSA) 2025;
[arXiv] -
Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhoň, Robert Tarjan, Jakub Tětek:
Fast and Simple Sorting Using Partial Information
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025;
[arXiv] -
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, Jukka Suomela
Online Locality Meets Distributed Quantum Computing
ACM Symposium on Theory of Computing (STOC) 2025;
[arXiv] -
Shyam Narayanan, Václav Rozhoň, Jakub Tětek, Mikkel Thorup:
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) [arXiv] -
Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan, Jakub Tětek:
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) [arXiv] -
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň:
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) [arXiv] -
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň:
Noisy k-means++ revisited
European Symposium on Algorithms (ESA) 2023;
[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] -
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;
[arXiv] -
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], [slides] -
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] -
Jan Grebík, Rachel Greenfeld, Václav Rozhoň, Terence Tao:
Measurable tilings by abelian group actions
International Mathematics Research Notices;
[arXiv] -
Christoph Grunau, Václav Rozhoň:
Adapting k-means Algorithms for Outliers
International Conference on Machine Learning (ICML) 2022;
[arXiv] -
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:
On Homomorphism Graphs
[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], [talk], [slides]
Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees
[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], [talk about the ID graph trick] [poster] -
Jan Grebík, Václav Rozhoň:
Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics
EUROCOMB 2021
[arXiv] -
Jan Grebík, Václav Rozhoň:
Local Problems on Grids from the Perspective of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
[arXiv], [talk] -
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň:
Improved Deterministic Network Decomposition
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021;
[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], [slides] -
Václav Rozhoň:
Simple and sharp analysis of k-means||
International Conference on Machine Learning (ICML) 2020;
[arXiv], [slides], [talk], -
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], [slides] -
Václav Rozhoň, Mohsen Ghaffari:
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Symposium on Theory of Computing (STOC) 2020;
[arXiv], [slides] [talk] -
Martin Doležal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhoň:
Cut distance identifying graphon parameters over weak* limits
Journal of Combinatorial Theory, series A;
[arXiv], [slides] -
Martin Doležal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhoň:
Relating the cut distance and the weak* topology for graphons
Journal of Combinatorial Theory, series B;
[arXiv] -
Václav Rozhoň:
A local approach to the Erdős-Sós conjecture
SIAM Journal on Discrete Mathematics;
[arXiv], [pdf], [slides] -
Tereza Klimošová, Diana Piguet, Václav Rozhoň:
A version of the Loebl-Komlós-Sós conjecture for skewed trees
EUROCOMB 2017, European Journal on Combinatorics for EUROCOMB 2017;
[arXiv], [extended abstract]