From the 1 of 11 linked papers with an AI index.
11 papers
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 paper analyzes the k-means++ seeding algorithm when the number of cluster centers is chosen uniformly at random from a range, showing it achieves a constant-factor approximatio…
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…
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…
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…