Zobrazeno 1 - 10
of 48
pro vyhledávání: '"Rozhon, Vaclav"'
Suppose we have a memory storing $0$s and $1$s and we want to estimate the frequency of $1$s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a block of $B$ bits at unit cost; not just one bit. If the input consists of
Externí odkaz:
http://arxiv.org/abs/2410.14643
While Dijkstra's algorithm has near-optimal time complexity for the problem of finding the shortest $st$-path, in practice, other algorithms are often superior on huge graphs. A prominent such example is the bidirectional search, which executes Dijks
Externí odkaz:
http://arxiv.org/abs/2410.14638
Autor:
Rozhoň, Václav
This text provides an introduction to the field of distributed local algorithms -- an area at the intersection of theoretical computer science and discrete mathematics. We collect many recent results in the area and demonstrate how they lead to a cle
Externí odkaz:
http://arxiv.org/abs/2406.19430
Autor:
Haeupler, Bernhard, Hladík, Richard, Iacono, John, Rozhon, Vaclav, Tarjan, Robert, Tětek, Jakub
We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple, natural deterministic algorithm that runs in $O(m+\log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of total
Externí odkaz:
http://arxiv.org/abs/2404.04552
Autor:
Akbari, Amirreza, Coiteux-Roy, Xavier, d'Amore, Francesco, Gall, François Le, Lievonen, Henrik, Melnyk, Darya, Modanese, Augusto, Pai, Shreyas, Renou, Marc-Olivier, Rozhoň, Václav, Suomela, Jukka
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent process
Externí odkaz:
http://arxiv.org/abs/2403.01903
We present a novel technique for work-efficient parallel derandomization, for algorithms that rely on the concentration of measure bounds such as Chernoff, Hoeffding, and Bernstein inequalities. Our method increases the algorithm's computational work
Externí odkaz:
http://arxiv.org/abs/2311.13764
This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure. Universal optimality is a powerful beyond-worst-case
Externí odkaz:
http://arxiv.org/abs/2311.11793
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate $k$-center solution during a sequence of $n$ point insertions and deletions while minimizing the recourse, i.e., the number of
Externí odkaz:
http://arxiv.org/abs/2307.13747
The $k$-means++ algorithm by Arthur and Vassilvitskii [SODA 2007] is a classical and time-tested algorithm for the $k$-means problem. While being very practical, the algorithm also has good theoretical guarantees: its solution is $O(\log k)$-approxim
Externí odkaz:
http://arxiv.org/abs/2307.13685
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorithmic power of these new notions and transformations. One application is
Externí odkaz:
http://arxiv.org/abs/2210.16351