5 papers
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…
Understanding Robust Catalytic Computing
Michal Koucký, Ian Mertz, Sasha Sami
Catalytic computing concerns space bounded computation which starts with memory full of data that have to be restored by the end of the computation. Lossy catalytic computing, defi…
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +4
A function is called an isometric embedding of the -dimensional Hamming metric space to the -dimensional edit metric space if, for all $x,y\in\{0…
Frontier Space-Time Algorithms Using Only Full Memory
Petr Chmel, Aditi Dudeja, Michal Koucký +2
We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only workspace, and use sublinear catalytic spa…
Many Flavors of Edit Distance
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +1
Several measures exist for string similarity, including notable ones like the edit distance and the indel distance. The former measures the count of insertions, deletions, and subs…