Showing 2026Show all
3 papers · 1 filter
cs.DS2026
Factor Three Approximation for Edit Distance
Egor Gorbachev
We give randomized algorithms for -approximate edit distance in time for unweighted edit distance and in …
cs.DS2026
The Sync Heap: Delete First, Ask Questions Later
Benjamin Aram Berendsohn, Egor Gorbachev, László Kozma
Heaps (priority queues) are among the best-studied data structures in computer science. In this paper, we critically revisit the textbook assumption that in the comparison model at…
cs.DS2026
Bottleneck Paths Reduce to Deterministic Graphical Games and a Counterexample to a Claimed Linear-Time Algorithm
Egor Gorbachev
Chechik, Kaplan, Thorup, Zamir, and Zwick (STACS 2016) claimed a simple deterministic linear-time comparison-based algorithm for solving deterministic two-player, turn-based, zero-…