Václav Rozhon

62 papers A* 20A 2B 1Journal 36Unranked 2

Year	Rank	Type	Title / Venue / Authors
2025	—	`conf`	Bidirectional Dijkstra's Algorithm is Instance-Optimal. SOSA Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2025	A*	`conf`	Fast and Simple Sorting Using Partial Information. SODA Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2025	J	`jnl`	Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond. ACM Trans. Algorithms Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, Václav Rozhon
2025	A*	`conf`	Online Locality Meets Distributed Quantum Computing. STOC 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
2024	J	`jnl`	Bidirectional Dijkstra's Algorithm is Instance-Optimal. CoRR Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2024	J	`jnl`	Fast and Simple Sorting Using Partial Information. CoRR Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2024	A*	`conf`	Fully Dynamic Consistent SODA Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, Václav Rozhon
2024	A*	`conf`	Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation. FOCS Shyam Narayanan, Václav Rozhon, Jakub Tetek, Mikkel Thorup
2024	J	`jnl`	Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation. CoRR Shyam Narayanan, Václav Rozhon, Jakub Tetek, Mikkel Thorup
2024	J	`jnl`	Invitation to Local Algorithms. CoRR Václav Rozhon
2024	—	`—`	Local Complexity: New Results and Bridges to Other Fields. Václav Rozhon
2024	J	`jnl`	Online Locality Meets Distributed Quantum Computing. CoRR 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
2024	A*	`conf`	Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps. FOCS Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2023	A*	`conf`	A Nearly Tight Analysis of Greedy k-means++. SODA Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon, Jakub Tetek
2023	—	`conf`	A Simple Deterministic Distributed Low-Diameter Clustering. SOSA Václav Rozhon, Bernhard Haeupler, Christoph Grunau
2023	J	`jnl`	Fully Dynamic Consistent k-Center Clustering. CoRR Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Václav Rozhon, Rajesh Jayaram
2023	A*	`conf`	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. SODA Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2023	A*	`conf`	Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond. SODA Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, Václav Rozhon
2023	A	`conf`	Noisy k-Means++ Revisited. ESA Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon
2023	J	`jnl`	Noisy k-means++ Revisited. CoRR Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon
2023	A*	`conf`	Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. STOC Václav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Zuzic
2023	J	`jnl`	Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps. CoRR Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2023	A*	`conf`	Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence. FOCS Mohsen Ghaffari, Christoph Grunau, Václav Rozhon
2023	J	`jnl`	Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence. CoRR Mohsen Ghaffari, Christoph Grunau, Václav Rozhon
2022	J	`jnl`	A Nearly Tight Analysis of Greedy k-means++. CoRR Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhon, Jakub Tetek
2022	J	`jnl`	A Simple Deterministic Distributed Low-Diameter Clustering. CoRR Václav Rozhon, Bernhard Haeupler, Christoph Grunau
2022	A*	`conf`	Adapting k-means Algorithms for Outliers. ICML Christoph Grunau, Václav Rozhon
2022	J	`jnl`	Cut distance identifying graphon parameters over weak* limits. J. Comb. Theory A Martin Dolezal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhon
2022	B	`conf`	Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. SPAA Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	J	`jnl`	Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. CoRR Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	J	`jnl`	Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees. CoRR Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2022	A*	`conf`	Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. FOCS Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler
2022	J	`jnl`	Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. CoRR Michael Elkin, Bernhard Haeupler, Václav Rozhon, Christoph Grunau
2022	J	`jnl`	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. CoRR Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	J	`jnl`	Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond. CoRR Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, Václav Rozhon
2022	A	`conf`	Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. ITCS Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2022	J	`jnl`	Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. CoRR Václav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Zuzic
2022	A*	`conf`	The Landscape of Distributed Complexities on Trees and Beyond. PODC Christoph Grunau, Václav Rozhon, Sebastian Brandt
2022	J	`jnl`	The Landscape of Distributed Complexities on Trees and Beyond. CoRR Christoph Grunau, Václav Rozhon, Sebastian Brandt
2022	A*	`conf`	Undirected (1+ STOC Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li
2022	J	`jnl`	Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms. CoRR Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li
2021	J	`jnl`	Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics. CoRR Jan Grebík, Václav Rozhon
2021	A*	`conf`	Improved Deterministic Network Decomposition. SODA Mohsen Ghaffari, Christoph Grunau, Václav Rozhon
2021	J	`jnl`	Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. CoRR Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2021	J	`jnl`	Of Toasts and Tails. CoRR Jan Grebík, Václav Rozhon
2021	J	`jnl`	On Homomorphism Graphs. CoRR Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky
2021	J	`jnl`	Relating the cut distance and the weak* topology for graphons. J. Comb. Theory B Martin Dolezal, Jan Grebík, Jan Hladký, Israel Rocha, Václav Rozhon
2021	A*	`conf`	The Randomized Local Computation Complexity of the Lovász Local Lemma. PODC Sebastian Brandt, Christoph Grunau, Václav Rozhon
2021	J	`jnl`	The randomized local computation complexity of the Lovász local lemma. CoRR Sebastian Brandt, Christoph Grunau, Václav Rozhon
2020	J	`jnl`	A version of the Loebl-Komlós-Sós conjecture for skew trees. Eur. J. Comb. Tereza Klimosová, Diana Piguet, Václav Rozhon
2020	J	`jnl`	Adapting k-means algorithms for outliers. CoRR Christoph Grunau, Václav Rozhon
2020	A*	`conf`	Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. PODC Sebastian Brandt, Christoph Grunau, Václav Rozhon
2020	J	`jnl`	Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma. CoRR Sebastian Brandt, Christoph Grunau, Václav Rozhon
2020	J	`jnl`	Improved Deterministic Network Decomposition. CoRR Mohsen Ghaffari, Christoph Grunau, Václav Rozhon
2020	A*	`conf`	Polylogarithmic-time deterministic network decomposition and distributed derandomization. STOC Václav Rozhon, Mohsen Ghaffari
2020	A*	`conf`	Simple and sharp analysis of k-means\|\|. ICML Václav Rozhon
2020	J	`jnl`	Simple and sharp analysis of k-means\|\|. CoRR Václav Rozhon
2020	A*	`conf`	k-means++: few more steps yield constant approximation. ICML Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhon
2020	J	`jnl`	k-means++: few more steps yield constant approximation. CoRR Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhon
2019	J	`jnl`	A Local Approach to the Erdös-Sós Conjecture. SIAM J. Discret. Math. Václav Rozhon
2019	J	`jnl`	Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. CoRR Václav Rozhon, Mohsen Ghaffari
2017	J	`jnl`	A skew version of the Loebl-Komlós-Sós conjecture. Electron. Notes Discret. Math. Tereza Klimosová, Diana Piguet, Václav Rozhon