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 [arXiv]
Bernhard Haeupler, Richar Hladík, Václav Rozhoň, Robert Tarjan, Jakub Tětek:
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps [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 [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]
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] 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]
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]
