2025 Theses Doctoral

New Frontiers in String Algorithms and Nearest Neighbour Search

Shekel Nosatzki, Negev

This thesis revolves arounds two main frameworks of problems: (i) String Problems, such as the Longest Increasing Subsequence (LIS), Longest Common Subsequence (LCS) and the Edit Distance (ED); and (ii) Approximate Nearest Neighbour Search Problems under different metrics.

For String Problems, we show the following results:* For ED, a constant approximation algorithm which runs in near-linear time. In particular, an algorithm for approximating the edit distance between two strings of length 𝑛 in time 𝑛¹⁺^𝜀 up to a constant factor, for any 𝜀 > 0.

* For parametrized LIS, the first sub-polynomial (in the parameter) approximation. In particular, we show that for any 𝑛 ∈ ℕ and 𝜆 = 𝑜(1), there exists a (randomized) 𝘯𝘰𝘯-𝘢𝘥𝘢𝘱𝘵𝘪𝘷𝘦 algorithm that, given a sequence of length 𝑛 with LIS ≥ 𝜆 𝑛, approximates the LIS up to a factor of 1/𝜆⁰⁽¹⁾ in 𝑛⁰⁽¹⁾ 𝜆 time.

* For LCS, we give the first sub-polynomial approximation in linear time.

For Approximate Nearest Neighbour Search Problems, we show the following results:* The first instance of a~simple, practical algorithm that provably leverages data-dependent hashing to improve upon data-oblivious LSH.

* We introduce the notion of metric embeddings into similarity measures over ℝ₊^𝑚, and use such new embeddings to develop Approximate Nearest Neighbor Search (ANN) algorithms which improve the approximation factor exponentially on the (longstanding) state-of-the-art on two important metrics:

* Edit distance over length-𝑘 strings: poly(log 𝑘) approximation;

* 𝓁_𝑝 over ℝ^𝑑, for 𝑝 > 2: 𝑂(log 𝑝) approximation (known to be asymptotically optimal in the relevant models of computation).

While the two frameworks might apriori feel unrelated, recent progress have shown they are ultimately intertwined. First and foremost, both frameworks have proven to be core problems in the area of fine-grained complexity, where conditional hardness has been shown under the Strong Exponential Time Hypothesis (SETH), among other conjectures. Second, the algorithmic techniques for solving the frameworks are inter-related, and we will use Similarity Search techniques to solve string problems and vice versa.