Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň:
Noisy k-means++ revisited
European Symposium on Algorithms (ESA) 2023;
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]
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.
