
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
We study connections between distributed local algorithms, finitary fact...
read it

The randomized local computation complexity of the Lovász local lemma
The Local Computation Algorithm (LCA) model is a popular model in the fi...
read it

Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics
We classify which local problems with inputs on oriented paths have soc...
read it

Of Toasts and Tails
We present an intimate connection among the following fields: (a) dist...
read it

Improved Deterministic Network Decomposition
Network decomposition is a central tool in distributed graph algorithms....
read it

Adapting kmeans algorithms for outliers
This paper shows how to adapt several simple and classical samplingbase...
read it

Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted ...
read it

Simple and sharp analysis of kmeans
We present a truly simple analysis of kmeans (Bahmani et al., PVLDB 2...
read it

kmeans++: few more steps yield constant approximation
The kmeans++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a sta...
read it

PolylogarithmicTime Deterministic Network Decomposition and Distributed Derandomization
We present a simple polylogarithmictime deterministic distributed algor...
read it
Václav Rozhoň
is this you? claim profile