Michael Elkin ® Bernhard Haeupler ® Václav Rozhoň ® Christoph Grunau:
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications [arXiv]
Jan Grebík, Rachel Greenfeld, Václav Rozhoň, Terence Tao:
Measurable tilings by abelian group actions [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
Submitted; [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]
Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Some time ago, I gave a very informal tutorial on what we knew about the relation of distributed algorithms, finitary factors, and descriptive combinatorics. Probably very outdated now.
Video 1,
Video 2,
Video 3,
Video 4,
Video 5,
Video 6.
Also, see this nice talk by Anton and this nice survey by Oleg Pikhurko about descriptive combinatorics.
