5 papers
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…
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-…
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
PaweÅ Gawrychowski, Egor Gorbachev, Tomasz Kociumaka
Min-plus matrix multiplication is used in many problems operating on distances in graphs or solvable by dynamic programming. Assuming the APSP hypothesis, there is no subcubic-time…
Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
Itai Boneh, Egor Gorbachev, Tomasz Kociumaka
The edit distance of two strings is the minimum number of character edits (insertions, deletions, and substitutions) needed to transform into . Its w…
Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
Egor Gorbachev, Tomasz Kociumaka
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions needed to transform one string into the other. The textbook algorithm determines…