Workshop Details

Pattern Matching with Edits is a classical string-processing problem that asks whether a length-n string T (the text) contains a substring whose edit distance to a length-m string P (the pattern) does not exceed a threshold k. Despite decades of research, we are still far from understanding the complexity of this problem as a function of m, n, and k; resolving this question remains one of the central open problems in the fine-grained complexity of string algorithms. In particular, we still do not know how many edits can be handled in near-linear time. The fastest known algorithm achieves near-linear complexity only for k = Õ(m^(2/7)), while the strongest conditional lower bound rules out such algorithms only for k > m^(1/2). In this talk, I will present the key algorithmic and combinatorial ideas behind the current state-of-the-art algorithms, as well as techniques that have emerged more recently from the study of Pattern Matching with Edits and its variants in a variety of computational settings. A recurring theme throughout these developments is the importance of understanding edit distance on dynamic and highly compressible strings.

We introduce the notion of metric embeddings into a similarity measure, such as the Jaccard coefficient. We develop average embeddings into similarity measures for a number of metric spaces, with (appropriately defined) distortion that is smaller than the best possible or known distortion of embedding into ell_1 or ell_2 spaces (bi-Lipschitz or average). We complement our embeddings with a new algorithm for Approximate Nearest Neighbor Search (ANNS) that leverages such an embedding.

Combining these results, we obtain new efficient algorithms for ANNS under the following two classic metrics, achieving an exponential improvement to longstanding prior work: 1) Edit distance over length-k strings: polylog(k) approximation; 2) ell_p over R^d, for p>2: O(log p) approximation (known to be asymptotically optimal in relevant models of computation).

Joint work with Negev Shekel Nosatzki.

Repetition is a defining characteristic of many modern string collections, particularly in genomics, where repositories may contain hundreds to thousands of closely related sequences. Exploiting this redundancy is essential for scaling classical string-processing algorithms beyond the limits of traditional approaches. To address this challenge, we developed Prefix-Free Parsing, a technique whose performance scales with the repetitiveness of the data and enables the efficient construction of compressed indexes and data structures. In this talk, I will introduce the core ideas behind Prefix-Free Parsing and discuss how it has transformed the construction of the Burrows-Wheeler Transform, FM-indexes, and other compressed representations for repetitive data. I will highlight applications to large genomic repositories, pangenome analysis, and population-scale sequence search, illustrating how compression can serve not only as a storage mechanism but also as an algorithmic tool. I will conclude with recent advances in recursive parsing and grammar-based compression, and discuss some open challenges.

We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only O(log(n)) workspace, and use sublinear catalytic space matching the best-known space bounds of non-catalytic algorithms running in polynomial time. First, we design a polynomial time algorithm for directed s-t connectivity using $n big/ 2^{Theta(sqrt{log n})}$ catalytic space, which matches the state-of-the-art time-space bounds in the non-catalytic setting [Barnes et al., 1998], and improves the catalytic space usage of the best known algorithm [Cook and Pyne, 2026]. Furthermore, using only O(log(n)) random bits we get a randomized algorithm whose running time nearly matches the fastest time bounds known for space-unrestricted algorithms. Second, we design polynomial time algorithms for the problems of computing Edit Distance, Longest Common Subsequence, and the Discrete Frechet Distance, again using $n big/ 2^{Theta(sqrt{log n})}$ catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021].

Rank aggregation asks how to combine several possibly inconsistent rankings into a single consensus ranking. Since rankings are permutations, they can also be viewed as ordered sequences, creating natural connections between rank aggregation, permutation metrics, and string algorithms. In this talk, I will discuss aggregation problems under several distance measures, including edit distance, Ulam distance, and Kendall tau distance, which capture different notions of disagreement between strings, permutations, and rankings. These distances arise in overlapping settings such as ranking, information retrieval, and computational biology. For all these metrics, the underlying optimization problems are NP-hard, while a simple 2-approximation often follows from the triangle inequality by returning an input ranking or sequence. The real bottleneck is to break this factor-2 barrier, and several recent works have made progress on this question for ranking problems in both approximation and scalable settings. I will discuss some of these developments, culminating in the 1-center objective for rank aggregation under Kendall tau distance: given several rankings, the goal is to find one ranking that minimizes the maximum distance to any input ranking. This center version is substantially more challenging than its median counterpart because the objective is governed by worst-case disagreement, and I will describe my recent work on breaking the factor-2 barrier for Kendall tau center.

Aggregating multiple input rankings over a set of candidates to generate a consensus ranking is one of the fundamental ranking problems, having many applications in social choice theory, hiring, college admission, web search, and databases. However, the optimal consensus ranking might be biased against any individual candidate or candidates belonging to certain marginalized communities or groups. This has motivated studies of the rank aggregation problem from the fairness perspective. While finding a consensus ranking, the additional objective is to ensure fair representation of each group in the top positions of the final aggregated ranking. In this talk, we will discuss various algorithms to find such a fair ranking approximately.

The classic exact pattern matching problem, given two strings -- a pattern P of length m and a text T of length n -- asks whether P occurs as a substring of T. A property tester for the problem needs to distinguish (with high probability) the following two cases for some threshold k: the YES case, where P occurs as a substring of T, and the NO case, where P has Hamming distance greater than k from every substring of T, that is, P has no k-mismatch occurrence in T. In this work, we provide adaptive and non-adaptive property testers for the exact pattern matching problem, jointly covering the whole spectrum of parameters. We further establish unconditional lower bounds demonstrating that the time and query complexities of our algorithms are optimal up to polylog(n) factors. Joint work with Tomasz Kociumaka https://arxiv.org/abs/2510.17645

The Tree Edit Distance (TED) between two rooted, ordered trees with n nodes labeled from an alphabet Σ is defined as the minimum cost to transform one tree into the other via a sequence of valid node insertions, deletions, and relabelings. First introduced by Selkow in the late 1970s, the algorithmic computation of TED has seen numerous improvements over the decades, culminating in an O(n³)-time algorithm [DMRW 2010]. In this presentation, we sketch the proof from our recent STOC 2025 paper showing that TED is fine-grained equivalent to the All-Pairs Shortest Path (APSP) problem. Our reduction is tight enough that, combined with the fastest APSP algorithm [Williams 2018], it yields the first slightly subcubic algorithm for TED, running in n³ / 2^(Ω(√(log n))) time. We also extend the proof to unweighted TED, where each edit costs one. Here, we achieve a runtime of O(n^((3+ω)/2)), matching the bound for the monotone min-plus product and closing the gap left by previous algorithms [Mao 2022, Dürr 2023] that incurred losses in their exponents.

String Edit Distance is a more-than-classical problem whose behavior in the dynamic setting, where the strings are updated over time, is well studied. A single-character substitution, insertion, or deletion can be processed in time Ohtilde(nw) when operation costs are positive integers bounded by w [Charalampopoulos, Kociumaka, Mozes, CPM 2020][Gorbachev, Kociumaka, STOC 2025]. If the weights are further uniform (insertions and deletions have equal cost), also an Ohtilde(nsqrt{n})-update time algorithm exists [Charalampopoulos, Kociumaka, Mozes, CPM 2020]. This is a substantial improvement over the static (n2) algorithm when w≪n or when we are dealing with uniform weights.

In contrast, for inherently related problems such as Tree Edit Distance, Dyck Edit Distance, and RNA Folding, it has remained unknown whether it is possible to devise dynamic algorithms with an advantage over the static algorithm. In this paper, we resolve this question by showing that (weighted) Tree Edit Distance, Dyck Edit Distance, and RNA Folding admit no dynamic speedup: under well-known fine-grained assumptions we show that the best possible algorithm recomputes the solution from scratch after each update. Furthermore, we prove a quadratic per-update lower bound for unweighted Tree Edit Distance under the k-Clique Conjecture. This provides the first separation between dynamic unweighted String Edit Distance and unweighted Tree Edit Distance, problems whose relative difficulty in the static setting is still open.

The size of datasets arising in algorithmic problems and data structures has grown rapidly and is expected to continue increasing. The texts involved are often several terabytes in size and can no longer fit in RAM. At the same time, many such datasets originate from highly repetitive sources, such as the 100K Genome Project or source code repositories. As a result, these inputs are often highly compressible, and their compressed representations can typically fit in RAM. Compressed Computation is a new paradigm for the design and analysis of algorithms and data structures, in which computation is performed directly on compressed representations of texts. This approach yields significantly faster and more space-efficient solutions than the naive strategy of first decompressing the data and then solving the problem. In this presentation, we will cover some recent hardness results on Compressed Computation.

The Closest String problem asks, given some input strings, to identify a single representative string that minimizes the maximum Hamming distance to the inputs. In this talk I will present some fine-grained algorithms and lower bounds, fully resolving the complexity of this fundamental problem for *binary* strings. For general alphabets, the picture is less clear and there remain some intriguing open questions. Based on joint work with Amir Abboud, Elazar Goldenberg, Mursalin Habib, Karthik C.S., and Ron Safier.