Václav Rozhoň

Follow

Generating author description...

All published works
Action Title Year Authors
+ PDF Chat Bidirectional Dijkstra’s Algorithm is Instance-Optimal 2025 Bernhard Haeupler
Richard Hladík
Václav Rozhoň
Robert E. Tarjan
Jakub Tětek
+ Online Locality Meets Distributed Quantum Computing 2024 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ň
+ PDF Chat Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation 2024 Shyam Narayanan
Václav Rozhoň
Jakub Tětek
Mikkel Thorup
+ PDF Chat Bidirectional Dijkstra's Algorithm is Instance-Optimal 2024 Bernhard Haeupler
Richard Hladík
Václav Rozhoň
Robert E. Tarjan
Jakub Tětek
+ PDF Chat Invitation to Local Algorithms 2024 Václav Rozhoň
+ PDF Chat Fast and Simple Sorting Using Partial Information 2024 Bernhard Haeupler
Richard Hladík
John Iacono
Václav Rozhoň
Robert E. Tarjan
Jakub Tětek
+ PDF ON HOMOMORPHISM GRAPHS 2024 Sebastian Brandt
Yi‐Jun Chang
Jan Grebík
Christoph Grunau
Václav Rozhoň
Zoltán Vidnyánszky
+ PDF Chat Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence 2023 Mohsen Ghaffari
Christoph Grunau
Václav Rozhoň
+ PDF Chat Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics 2023 Jan Grebík
Václav Rozhoň
+ Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances 2023 Václav Rozhoň
Bernhard Haeupler
Anders Martinsson
Christoph Grunau
Goran Žužić
+ PDF Measurable Tilings by Abelian Group Actions 2023 Jan Grebík
Rachel Greenfeld
Václav Rozhoň
Terence Tao
+ PDF Chat Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization 2023 Mohsen Ghaffari
Christoph Grunau
Bernhard Haeupler
Saeed Ilchi
Václav Rozhoň
+ PDF Chat Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond 2023 Salwa Faour
Mohsen Ghaffari
Christoph Grunau
Fabian Kühn
Václav Rozhoň
+ PDF Chat A Nearly Tight Analysis of Greedy k-means++ 2023 Christoph Grunau
Ahmet Alper Özüdoğru
Václav Rozhoň
Jakub Tětek
+ Noisy k-means++ Revisited 2023 Christoph Grunau
Ahmet Alper Özüdoğru
Václav Rozhoň
+ Fully Dynamic Consistent $k$-Center Clustering 2023 Jakub Łącki
Bernhard Haeupler
Christoph Grunau
Václav Rozhoň
Rajesh Jayaram
+ Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps 2023 Bernhard Haeupler
Richard Hladík
Václav Rozhoň
Robert E. Tarjan
Jakub Tětek
+ Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence 2023 Mohsen Ghaffari
Christoph Grunau
Václav Rozhoň
+ PDF Chat Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications 2022 Václav Rozhoň
Michael Elkin
Christoph Grunau
Bernhard Haeupler
+ PDF The Landscape of Distributed Complexities on Trees and Beyond 2022 Christoph Grunau
Václav Rozhoň
Sebastian Brandt
+ PDF Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates 2022 Marcel Bezdrighin
Michael Elkin
Mohsen Ghaffari
Christoph Grunau
Bernhard Haeupler
Saeed Ilchi
Václav Rozhoň
+ PDF Chat Cut distance identifying graphon parameters over weak* limits 2022 Martin Doležal
Jan Grebík
Jan Hladký
Israel Rocha
Václav Rozhoň
+ Undirected $(1+\varepsilon)$-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms 2022 Václav Rozhoň
Christoph Grunau
Bernhard Haeupler
Goran Žužić
Jason Li
+ Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees 2022 Sebastian Brandt
Yi‐Jun Chang
Jan Grebík
Christoph Grunau
Václav Rozhoň
Zoltán Vidnyánszky
+ Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications 2022 Michael Elkin
Bernhard Haeupler
Václav Rozhoň
Christoph Grunau
+ Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates 2022 Marcel Bezdrighin
Michael Elkin
Mohsen Ghaffari
Christoph Grunau
Bernhard Haeupler
Saeed Ilchi
Václav Rozhoň
+ The Landscape of Distributed Complexities on Trees and Beyond 2022 Christoph Grunau
Václav Rozhoň
Sebastian Brandt
+ Measurable tilings by abelian group actions 2022 Jan Grebík
Rachel Greenfeld
Václav Rozhoň
Terence Tao
+ A Nearly Tight Analysis of Greedy k-means++ 2022 Christoph Grunau
Ahmet Alper Özüdoğru
Václav Rozhoň
Jakub Tětek
+ Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization 2022 Mohsen Ghaffari
Christoph Grunau
Bernhard Haeupler
Saeed Ilchi
Václav Rozhoň
+ Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond 2022 Salwa Faour
Mohsen Ghaffari
Christoph Grunau
Fabian Kühn
Václav Rozhoň
+ A Simple Deterministic Distributed Low-Diameter Clustering 2022 Václav Rozhoň
Bernhard Haeupler
Christoph Grunau
+ Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances 2022 Václav Rozhoň
Bernhard Haeupler
Anders Martinsson
Christoph Grunau
Goran Žužić
+ On Homomorphism Graphs. 2021 Sebastian Brandt
Yi‐Jun Chang
Jan Grebík
Christoph Grunau
Václav Rozhoň
Zoltán Vidnyánszky
+ PDF Chat The Randomized Local Computation Complexity of the Lovász Local Lemma 2021 Sebastian Brandt
Christoph Grunau
Václav Rozhoň
+ The randomized local computation complexity of the Lov\'asz local lemma 2021 Sebastian Brandt
Christoph Grunau
Václav Rozhoň
+ Of Toasts and Tails. 2021 Jan Grebík
Václav Rozhoň
+ PDF Improved Deterministic Network Decomposition 2021 Mohsen Ghaffari
Christoph Grunau
Václav Rozhoň
+ PDF Chat Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics 2021 Jan Grebík
Václav Rozhoň
+ Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics 2021 Sebastian Brandt
Yi‐Jun Chang
Jan Grebík
Christoph Grunau
Václav Rozhoň
Zoltán Vidnyánszky
+ The randomized local computation complexity of the Lovász local lemma 2021 Sebastian Brandt
Christoph Grunau
Václav Rozhoň
+ Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics 2021 Jan Grebík
Václav Rozhoň
+ On Homomorphism Graphs 2021 Sebastian Brandt
Yi‐Jun Chang
Jan Grebík
Christoph Grunau
Václav Rozhoň
Zoltán Vidnyánszky
+ Local Problems on Grids from the Perspective of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics 2021 Jan Grebík
Václav Rozhoň
+ PDF Chat Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma 2020 Sebastian Brandt
Christoph Grunau
Václav Rozhoň
+ Adapting k-means algorithms for outliers. 2020 Christoph Grunau
Václav Rozhoň
+ PDF Chat Polylogarithmic-time deterministic network decomposition and distributed derandomization 2020 Václav Rozhoň
Mohsen Ghaffari
+ PDF Chat Relating the cut distance and the weak* topology for graphons 2020 Martin Doležal
Jan Grebík
Jan Hladký
Israel Rocha
Václav Rozhoň
+ A version of the Loebl–Komlós–Sós conjecture for skew trees 2020 Tereza Klimošová
Diana Piguet
Václav Rozhoň
+ Simple and sharp analysis of k-means|| 2020 Václav Rozhoň
+ k-means++: few more steps yield constant approximation 2020 Davin Choo
Christoph Grunau
Julian Portmann
Václav Rozhoň
+ Improved Deterministic Network Decomposition 2020 Mohsen Ghaffari
Christoph Grunau
Václav Rozhoň
+ Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma 2020 Sebastian Brandt
Christoph Grunau
Václav Rozhoň
+ Adapting $k$-means algorithms for outliers 2020 Christoph Grunau
Václav Rozhoň
+ A Local Approach to the Erdös--Sós Conjecture 2019 Václav Rozhoň
+ Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization 2019 Václav Rozhoň
Mohsen Ghaffari
+ Cut distance identifying graphon parameters over weak* limits 2018 Martin Doležal
Jan Grebík
Jan Hladký
Israel Rocha
Václav Rozhoň
+ Sufficient conditions for embedding trees 2018 Václav Rozhoň
+ A local approach to the Erd\H{o}s-S\'os conjecture 2018 Václav Rozhoň
+ A version of the Loebl-Koml\'os-S\'os conjecture for skewed trees 2018 Tereza Klimošová
Diana Piguet
Václav Rozhoň
+ A local approach to the Erdős-Sós conjecture 2018 Václav Rozhoň
+ A version of the Loebl-Komlós-Sós conjecture for skewed trees 2018 Tereza Klimošová
Diana Piguet
Václav Rozhoň
+ A skew version of the Loebl–Komlós–Sós conjecture 2017 Tereza Klimošová
Diana Piguet
Václav Rozhoň
Common Coauthors
Commonly Cited References
Action Title Year Authors # of times referenced
+ PDF Chat Polylogarithmic-time deterministic network decomposition and distributed derandomization 2020 Václav Rozhoň
Mohsen Ghaffari
7
+ PDF BROOKS’ THEOREM FOR MEASURABLE COLORINGS 2016 Clinton T. Conley
Andrew Marks
Robin Tucker-Drob
7
+ PDF Chat On Derandomizing Local Distributed Algorithms 2018 Mohsen Ghaffari
David G. Harris
Fabian Kühn
7
+ PDF Chat A Time Hierarchy Theorem for the LOCAL Model 2017 Yi‐Jun Chang
Seth Pettie
6
+ PDF Improved Deterministic Network Decomposition 2021 Mohsen Ghaffari
Christoph Grunau
Václav Rozhoň
6
+ A determinacy approach to Borel combinatorics 2015 Andrew Marks
6
+ PDF Chat A lower bound for the distributed Lovász local lemma 2016 Sebastian Brandt
Orr Fischer
Juho Hirvonen
Barbara Keller
Tuomo Lempiäinen
Joel Rybicki
Jukka Suomela
Jara Uitto
6
+ Borel structurability on the 2-shift of a countable group 2015 Brandon Seward
Robin Tucker-Drob
6
+ PDF Chat An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model 2016 Yi‐Jun Chang
Tsvi Kopelowitz
Seth Pettie
6
+ Borel Chromatic Numbers 1999 Alexander S. Kechris
Sławomir Solecki
Stevo Todorčević
5
+ PDF Chat A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma 2019 Sebastian Brandt
Yannic Maus
Jara Uitto
5
+ PDF Chat The Approximate Loebl--Komlós--Sós Conjecture III: The Finer Structure of LKS Graphs 2017 Jan Hladký
János Komlós
Diana Piguet
Miklós Simonovits
Maya Stein
Endre Szemerédi
5
+ PDF Chat Borel circle squaring 2017 Andrew Marks
Spencer Unger
4
+ Faster parallel algorithm for approximate shortest path 2020 Jason Li
4
+ PDF Chat Hyperfiniteness and Borel combinatorics 2019 Clinton T. Conley
Steve Jackson
Andrew Marks
Brandon Seward
Robin Tucker-Drob
4
+ What Can be Computed Locally? 1995 Moni Naor
Larry Stockmeyer
4
+ PDF Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems 2020 Will Rosenbaum
Jukka Suomela
4
+ COUNTABLE BOREL EQUIVALENCE RELATIONS 2002 Stephen Jackson
Alexander S. Kechris
Alain Louveau
4
+ Loebl–Komlós–Sós Conjecture: Dense case 2015 Jan Hladký
Diana Piguet
4
+ PDF Chat An approximate version of the Loebl–Komlós–Sós conjecture 2011 Diana Piguet
Maya Stein
4
+ PDF Measurable circle squaring 2017 Łukasz Grabowski
András Máthé
Oleg Pikhurko
4
+ Proof of the Loebl–Komlós–Sós conjecture for large, dense graphs 2009 Oliver Cooley
4
+ PDF Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms 2023 Anton Bernshteyn
4
+ PDF Chat The Approximate Loebl--Komlós--Sós Conjecture IV: Embedding Techniques and the Proof of the Main Result 2017 Jan Hladký
János Komlós
Diana Piguet
Miklós Simonovits
Maya Stein
Endre Szemerédi
4
+ PDF Chat Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics 2021 Jan Grebík
Václav Rozhoň
4
+ PDF Chat Counterexamples to Hedetniemi's conjecture 2019 Yaroslav Shitov
4
+ PDF Chat On the complexity of local distributed graph problems 2017 Mohsen Ghaffari
Fabian Kühn
Yannic Maus
4
+ Continuous Combinatorics of Abelian Group Actions 2018 Su Gao
Steve Jackson
Edward Krohne
Brandon Seward
4
+ Finitary coloring 2017 Alexander E. Holroyd
Oded Schramm
David B. Wilson
4
+ Equidecomposability and discrepancy; a solution of Tarski's circle-squaring problem 1990 Miklós Laczkovich
4
+ PDF FINITELY DEPENDENT COLORING 2016 Alexander E. Holroyd
Thomas M. Liggett
4
+ PDF Chat The Approximate Loebl--Komlós--Sós Conjecture II: The Rough Structure of LKS Graphs 2017 Jan Hladký
János Komlós
Diana Piguet
Miklós Simonovits
Maya Stein
Endre Szemerédi
4
+ A coloring property for countable groups 2009 Su Gao
Steve Jackson
Brandon Seward
3
+ PDF Chat Limits of locally–globally convergent graph sequences 2014 Hamed Hatami
László Lovász
Balázs Szegedy
3
+ Graph limits and exchangeable random graphs 2007 Persi Diaconis
Svante Janson
3
+ PDF Finitely dependent processes are finitary 2020 Yinon Spinka
3
+ REGULAR PARTITIONS OF GRAPHS 1975 Endre Szemerédi
3
+ A fast and simple randomized parallel algorithm for the maximal independent set problem 1986 Noga Alon
László Babai
Alon Itai
3
+ PDF Proof of the $(n/2-n/2-n/2)$ Conjecture for Large $n$ 2011 Yi Zhao
3
+ PDF On the structure of linear graphs 1946 Paul Erdös
A. H. Stone
3
+ PDF Chat Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing 2008 Christian Borgs
Jennifer Chayes
L. Lovász
Vera T. Sós
K. Vesztergombi
3
+ Noisy, Greedy and Not So Greedy k-means++ 2019 Anup Bhattacharya
Jan Eube
Heiko Röglin
Melanie Schmidt
3
+ Distributed Algorithms, the Lov\'{a}sz Local Lemma, and Descriptive Combinatorics 2020 Anton Bernshteyn
3
+ PDF Chat Limits of dense graph sequences 2006 László Lovász
Balázs Szegedy
3
+ Borel sets and Ramsey's theorem 1973 Fred Galvin
Karel Prikry
3
+ The step Sidorenko property and non-norming edge-transitive graphs 2018 Daniel Kráľ
Táısa Martins
Péter Pál Pach
Marcin Wrochna
3
+ PDF Szemerédi’s Lemma for the Analyst 2007 László Lovász
Balázs Szegedy
3
+ A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function 2019 Claude Tardif
Xuding Zhu
3
+ Distributed Degree Splitting, Edge Coloring, and Orientations 2017 Mohsen Ghaffari
Hsin-Hao Su
3
+ Cut-norm and entropy minimization over weak⁎ limits 2019 Martin Doležal
Jan Hladký
3