Václav Rozhoň
I am fortunate to be a PhD student in the group of Mohsen Ghaffari at ETH, Zurich.
Before coming to ETH, I studied at Charles University, Prague and worked in the group of Diana Piguet.
If you wish to contact me, please use my email [name][surname]@gmail.com
Teaching
Principles of distributed computing (teaching assistant, Spring 2021)
Advanced algorithms (teaching assistant, Fall 2020)
Principles of distributed computing (teaching assistant, Spring 2020)
Advanced algorithms (teaching assistant, Fall 2019)
Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Recently, I gave a very informal tutorial on the relation of distributed algorithms, finitary factors, and descriptive combinatorics. Understanding of the connection between these fields started in an insightful work of Anton Bernshteyn. In the tutorials I focused on some work Jan Grebík and I did. The tutorials probably contain many inaccuraccies/mistakes as I am learning the fields myself. :) It is also presented from a computer science perspective to other computer scientists. Finally, it is very informal. Still, I hope the recordings could be useful to other people as well.
Also, see this nice talk by Anton and this nice survey by Oleg Pikhurko about descriptive combinatorics.
 Tutorial 1: I started with a concrete example of the usefulness of the link between descriptive combinatorics and distributed algorithms. I talked about how the very nice work of Marks from descriptive combinatorics gives a fresh look on the famous round elimination lower bound for sinkless orientation and how it can be used to get new lower bounds for trees that we do not know how to get via round elimination. I did not use the descriptive combinatorics language and the rest of the tutorials are independent of this one.
 Tutorial 2:
I talked about splitting a cycle into intervals. This is the easiest descriptive combinatorics setup. We saw that for local problems, this setup is the same as the setup of local problems on oriented paths known in the distributed computing. This example is also discussed in the survey of Pikhurko and in the intro of this paper.
 Tutorial 3:
I tried to motivate general Borel constructions (see the survey of Pikhurko). I gave an example of a local problem on a path with inputs (from here) and a local problem on a tree without inputs that allow a Borel construction but not a local one.
 Tutorial 4:
In this tutorial, I discussed the circle squaring problem that motivates the area of descriptive combinatorics. Then, we switched topics and I discussed the Ising model to motivate the study of finitary factors. We finished with discussing the connection of finitary factors to oblivious algorithms and we discussed the oblivious variant of Linial's coloring algorithm.
 Tutorial 5:
I discussed various basic results regarding the tail complexity of oblivious algorithms (see this and this) and how it relates to the classical local complexity.
 Tutorial 6:
I discussed the tail complexity of constructing the toast in grids (see this). The discussion diverged to various open problems.
Papers
My Google Scholar page

Sebastian Brandt, Christoph Grunau, Václav Rozhoň:
The randomized local computation complexity of the Lovász local lemma
[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
[arXiv]

Jan Grebík, Václav Rozhoň:
Of Toasts and Tails
[arXiv]

Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň:
Improved Deterministic Network Decomposition
ACMSIAM 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 kmeans
International Conference on Machine Learning (ICML) 2020;
[arXiv],
[slides],
[video],

Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhoň:
kmeans++: few more steps yield constant approximation
International Conference on Machine Learning (ICML) 2020;
[arXiv],
[slides]

Václav Rozhoň, Mohsen Ghaffari:
PolylogarithmicTime Deterministic Network Decomposition and Distributed Derandomization
Symposium on Theory of Computing (STOC) 2020;
[arXiv],
[slides]
[video]

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ősSós conjecture
SIAM Journal on Discrete Mathematics;
[arXiv],
[pdf],
[slides]

Tereza Klimošová, Diana Piguet, Václav Rozhoň:
A version of the LoeblKomlósSós conjecture for skewed trees
EUROCOMB 2017, European Journal on Combinatorics for EUROCOMB 2017;
[arXiv]
Other reports

Master thesis.
[pdf]

Study text about probability for high school students (in Czech)
[1,2,3]

Bachelor thesis.
[pdf]
[slides]