Václav Rozhon

According to our database, Václav Rozhon authored at least 33 papers between 2017 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Online Locality Meets Distributed Quantum Computing.

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 Rozhon, Jukka Suomela

CoRR, 2024

Fully Dynamic Consistent <i>k</i>-Center Clustering.

Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, Václav Rozhon

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps.

Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek

CoRR, 2023

Fully Dynamic Consistent k-Center Clustering.

Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Václav Rozhon, Rajesh Jayaram

CoRR, 2023

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances.

Václav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Zuzic

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Simple Deterministic Distributed Low-Diameter Clustering.

Václav Rozhon, Bernhard Haeupler, Christoph Grunau

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Nearly Tight Analysis of Greedy k-means++.

Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon, Jakub Tetek

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond.

Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, Václav Rozhon

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization.

Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence.

Mohsen Ghaffari, Christoph Grunau, Václav Rozhon

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Noisy k-Means++ Revisited.

Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Cut distance identifying graphon parameters over weak* limits.

Martin Dolezal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhon

J. Comb. Theory, Ser. A, 2022

Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees.

Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky

CoRR, 2022

Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms.

Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li

CoRR, 2022

Undirected (1+<i>ε</i>)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms.

Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates.

Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

The Landscape of Distributed Complexities on Trees and Beyond.

Christoph Grunau, Václav Rozhon, Sebastian Brandt

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics.

Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Adapting k-means Algorithms for Outliers.

Christoph Grunau, Václav Rozhon

Proceedings of the International Conference on Machine Learning, 2022

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications.

Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Relating the cut distance and the weak* topology for graphons.

Martin Dolezal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhon

J. Comb. Theory, Ser. B, 2021

On Homomorphism Graphs.

Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky

CoRR, 2021

Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics.

Jan Grebík, Václav Rozhon

CoRR, 2021

Of Toasts and Tails.

Jan Grebík, Václav Rozhon

CoRR, 2021

Improved Deterministic Network Decomposition.

Mohsen Ghaffari, Christoph Grunau, Václav Rozhon

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Randomized Local Computation Complexity of the Lovász Local Lemma.

Sebastian Brandt, Christoph Grunau, Václav Rozhon

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

A version of the Loebl-Komlós-Sós conjecture for skew trees.

Tereza Klimosová, Diana Piguet, Václav Rozhon

Eur. J. Comb., 2020

Polylogarithmic-time deterministic network decomposition and distributed derandomization.

Václav Rozhon, Mohsen Ghaffari

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma.

Sebastian Brandt, Christoph Grunau, Václav Rozhon

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Simple and sharp analysis of k-means||.

Václav Rozhon

Proceedings of the 37th International Conference on Machine Learning, 2020

k-means++: few more steps yield constant approximation.

Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhon

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

A Local Approach to the Erdös-Sós Conjecture.

Václav Rozhon

SIAM J. Discret. Math., 2019

2017

A skew version of the Loebl-Komlós-Sós conjecture.

Tereza Klimosová, Diana Piguet, Václav Rozhon

Electron. Notes Discret. Math., 2017