Egor Gorbachev

activity

20232026

collaborators

8 papers

cs.DS2026

Factor Three Approximation for Edit Distance

Egor Gorbachev

We give randomized algorithms for $3$ -approximate edit distance in $O (N^{11/6})$ time for unweighted edit distance and in $O (N^{40/21})$ …

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-…

cs.DS2025

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds

Itai Boneh, Egor Gorbachev, Tomasz Kociumaka

The edit distance $e d (X, Y)$ of two strings $X, Y \in Σ^{*}$ is the minimum number of character edits (insertions, deletions, and substitutions) needed to transform $X$ into $Y$ . Its we…

cs.DS2024

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…

cs.DS2024

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends

Karl Bringmann, Egor Gorbachev

In an $m$ -edge host graph $G$ , all triangles can be listed in time $O (m^{1.5})$ [Itai, Rodeh '78], and all $k$ -cycles can be listed in time $O (m^{2 - 1/ ⌈ k /2 ⌉} + t)$ whe…

cs.DS2024

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…

cs.CG2023

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions $d \geq 4$

Egor Gorbachev, Marvin Künnemann

Klee's measure problem (computing the volume of the union of $n$ axis-parallel boxes in $R^{d}$ ) is well known to have $n^{\frac{d}{2} \pm o (1)}$ -time algorithms (Overmars, Y…

Factor Three Approximation for Edit Distance

The Sync Heap: Delete First, Ask Questions Later

Bottleneck Paths Reduce to Deterministic Graphical Games and a Counterexample to a Claimed Linear-Time Algorithm

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d≥4

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions $d \geq 4$