Václav Rozhoň | DeepAI

DeepAI AI Chat

Featured Co-authors

Jason Li
55 publications
Fabian Kuhn
43 publications
Mohsen Ghaffari
41 publications
Bernhard Haeupler
39 publications
Christoph Grunau
28 publications
Sebastian Brandt
28 publications
Yi-Jun Chang
24 publications
Rajesh Jayaram
24 publications
Jakub Łącki
18 publications
Jakub Tětek
17 publications
Goran Zuzic
16 publications

∙ 07/25/2023

Fully Dynamic Consistent k-Center Clustering

We study the consistent k-center clustering problem. In this problem, th...

0 Jakub Łącki, et al. ∙

∙ 07/25/2023

Noisy k-means++ Revisited

The k-means++ algorithm by Arthur and Vassilvitskii [SODA 2007] is a cla...

0 Christoph Grunau, et al. ∙

∙ 10/28/2022

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances

We introduce stronger notions for approximate single-source shortest-pat...

0 Václav Rozhoň, et al. ∙

∙ 10/21/2022

A Simple Deterministic Distributed Low-Diameter Clustering

We give a simple, local process for nodes in an undirected graph to form...

0 Václav Rozhoň, et al. ∙

∙ 09/23/2022

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization

This paper presents significantly improved deterministic algorithms for ...

0 Mohsen Ghaffari, et al. ∙

∙ 09/23/2022

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond

We develop a general deterministic distributed method for locally roundi...

0 Salwa Faour, et al. ∙

∙ 07/16/2022

A Nearly Tight Analysis of Greedy k-means++

The famous k-means++ algorithm of Arthur and Vassilvitskii [SODA 2007] i...

0 Christoph Grunau, et al. ∙

∙ 04/29/2022

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates

This paper presents efficient distributed algorithms for a number of fun...

0 Marcel Bezdrighin, et al. ∙

∙ 04/20/2022

Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees

We study complexity classes of local problems on regular trees from the ...

0 Sebastian Brandt, et al. ∙

∙ 04/18/2022

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications

This paper presents new deterministic and distributed low-diameter decom...

0 Michael Elkin, et al. ∙

∙ 04/12/2022

Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel Distributed Algorithms

This paper presents near-optimal deterministic parallel and distributed ...

0 Václav Rozhoň, et al. ∙

∙ 02/09/2022

The Landscape of Distributed Complexities on Trees and Beyond

We study the local complexity landscape of locally checkable labeling (L...

0 Christoph Grunau, et al. ∙

∙ 11/05/2021

On Homomorphism Graphs

We introduce a new type of examples of bounded degree acyclic Borel grap...

0 Sebastian Brandt, et al. ∙

∙ 06/03/2021

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

We study connections between distributed local algorithms, finitary fact...

0 Sebastian Brandt, et al. ∙

∙ 03/30/2021

The randomized local computation complexity of the Lovász local lemma

The Local Computation Algorithm (LCA) model is a popular model in the fi...

0 Sebastian Brandt, et al. ∙

∙ 03/25/2021

Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics

We classify which local problems with inputs on oriented paths have so-c...

0 Jan Grebík, et al. ∙

∙ 03/15/2021

Of Toasts and Tails

We present an intimate connection among the following fields: (a) dist...

0 Jan Grebík, et al. ∙

∙ 07/16/2020

Improved Deterministic Network Decomposition

Network decomposition is a central tool in distributed graph algorithms....

0 Mohsen Ghaffari, et al. ∙

∙ 07/02/2020

Adapting k-means algorithms for outliers

This paper shows how to adapt several simple and classical sampling-base...

0 Christoph Grunau, et al. ∙

∙ 06/08/2020

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 ...

0 Sebastian Brandt, et al. ∙

∙ 03/05/2020

Simple and sharp analysis of k-means||

We present a truly simple analysis of k-means|| (Bahmani et al., PVLDB 2...

0 Václav Rozhoň, et al. ∙

∙ 02/18/2020

k-means++: few more steps yield constant approximation

The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a sta...

0 Davin Choo, et al. ∙

∙ 07/25/2019

Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization

We present a simple polylogarithmic-time deterministic distributed algor...

0 Václav Rozhoň, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world