2 citations · 3 across the 13 of their papers we have counts for
20 papers
General Constructions of Permutation-Fair Dice
Tomáš Gavenčiak, Bernhard Haeupler, Václav Rozhoň
Suppose that each of players rolls a different die and the players are ordered by their rolls. Can the dice use disjoint labels such that ties are impossible, while all or…
Fluctuations of Nonlinear Observables in Mean Field Neural Network Training
Arnaud Descours, Geoffrey Lacour
Mean field limits describe the training dynamics of wide neural networks through the evolution of the empirical distribution of their parameters. Although functional central limit…
Collision Detection is Instance ptimal Under the Birthday Threshold
Omri Ben-Eliezer, Tomer Grossman, Václav Rozhoň +1
Can structural knowledge about a hash function help accelerate the (black box) detection of collisions in it? This question is fundamental to cryptography theory given the importan…
Test or Run? Scheduling Jobs of Unknown Length
Václav Rozhoň
A machine faces many jobs whose lengths are hidden. Spending one unit of time to inspect a job may reveal a short job that should be finished now, or it may reveal nothing useful w…
Borel dimension growth and hyperfiniteness
Jan Grebík, Andrew S. Marks, Václav Rozhoň +1
We show that every increasing union of Borel graphs of pointwise volume growth at most is hyperfinite, where is the unique real root of $(1 - γ)^3…
Randomizing the Number of Centers in k-means++
Vaclav Rozhon
The -means++ algorithm is a standard and widely used seeding method for -means clustering, but for a fixed number of centers its worst-case expected approximation ratio i…
Heaps and Their Working Sets
Bernhard Haeupler, Richard Hladík, Václav Rozhoň +1
We construct a heap with strong beyond-worst-case performance guarantees and explore the analysis of such heaps. First, we unify existing notions of the working-set bound for heaps…
Splay trees are almost dynamically optimal
Petr Chmel, Bernhard Haeupler, Richard Hladík +5
Sleator and Tarjan [JACM, 1985] conjectured that splay trees are dynamically optimal -- that on every access sequence, they perform within a constant factor of the optimal offline…
Bolzano: Case Studies in LLM-Assisted Mathematical Research
Martin Balko, Jan Grebík, Pavel Hubáček +5
We report new results on eight problems in mathematics and theoretical computer science, produced with the assistance of Bolzano, an open-source multi-agent LLM system. Bolzano orc…
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan, Václav Rozhoň, Jakub Tětek +1
Suppose we have a memory storing s and s and we want to estimate the frequency of s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a bloc…
Bidirectional Dijkstra's Algorithm is Instance-Optimal
Bernhard Haeupler, Richard Hladík, Vaclav Rozhon +2
Although Dijkstra's algorithm has near-optimal time complexity for the problem of finding a shortest path from a given vertex to a given vertex , in practice other algorithm…
Invitation to Local Algorithms
Václav Rozhoň
This text provides an introduction to distributed local algorithms -- an area at the intersection of theoretical computer science and discrete mathematics. We collect recent result…
Fast and Simple Sorting Using Partial Information
Bernhard Haeupler, Richard Hladík, John Iacono +3
We consider the problem of sorting items, given the outcomes of pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T…
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore +8
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-s…
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
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…
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler, Richard Hladík, Václav Rozhoň +2
In this paper we prove that Dijkstra's shortest-path algorithm, if implemented with a sufficiently efficient heap, is universally optimal in its running time, and with suitable sma…
Fully Dynamic Consistent -Center Clustering
Jakub Łącki, Bernhard Haeupler, Christoph Grunau +2
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate -center solution during a sequence of point inser…
Noisy k-means++ Revisited
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň
The -means++ algorithm by Arthur and Vassilvitskii [SODA 2007] is a classical and time-tested algorithm for the -means problem. While being very practical, the algorithm also…
The Landscape of Distributed Complexities on Trees and Beyond
Christoph Grunau, Vaclav Rozhon, Sebastian Brandt
We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below . Our contribution is th…
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Sebastian Brandt, Yi-Jun Chang, Jan Grebík +3
We study connections between distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics in the context of regular trees. We extend the Borel det…