Jakob Nogler

STOC Conference 2025 Conference Paper

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence

• Jakob Nogler
• Adam Polak 0001
• Barna Saha
• Virginia Vassilevska Williams
• Yinzhan Xu
• Christopher Ye 0001

The tree edit distance (TED) between two rooted ordered trees with n nodes labeled from an alphabet Σ is the minimum cost of transforming one tree into the other by a sequence of valid operations consisting of insertions, deletions and relabeling of nodes. The tree edit distance is a well-known generalization of string edit distance and has been studied since the 1970s. Its running time has seen steady improvements starting with an O ( n 6 ) algorithm [Tai, J.ACM 1979], improved to O ( n 4 ) [Shasha, Zhang, SICOMP 1989] and to O ( n 3 log n ) [Klein, ESA 1998], and culminating in an O ( n 3 ) algorithm [Demaine, Mozes, Rossman, Weimann, ACM TALG 2010]. The latter is known to be optimal for any dynamic programming based algorithm that falls under a certain decomposition framework that captures all known sub- n 4 time algorithms. Fine-grained complexity casts further light onto this hardness showing that a truly subcubic time algorithm for TED implies a truly subcubic time algorithm for All-Pairs Shortest Paths (APSP) [Bringmann, Gawrychowski, Mozes, Weimann, ACM TALG 2020]. Therefore, under the popular APSP hypothesis, a truly subcubic time algorithm for TED cannot exist. However, unlike many problems in fine-grained complexity for which conditional hardness based on APSP also comes with equivalence to APSP, whether TED can be reduced to APSP has remained unknown. In this paper, we resolve this. Not only we show that TED is fine-grained equivalent to APSP, our reduction is tight enough, so that combined with the fastest APSP algorithm to-date [Williams, SICOMP 2018] it gives the first ever subcubic time algorithm for TED running in n 3 /2 Ω(√log n ) time. We also consider the unweighted tree edit distance problem in which the cost of each edit (insertion, deletion, and relabeling) is one. For unweighted TED, a truly subcubic algorithm is known due to Mao [Mao, FOCS 2022], and later improved slightly by Dürr [Dürr, IPL 2023] to run in O ( n 2.9148 ) time. Since their algorithm uses bounded monotone min-plus product as a crucial subroutine, and the best running time for this product is Õ( n 3+ω/2 )≤ O ( n 2.6857 ) (where ω is the exponent of fast matrix multiplication), the much higher running time of unweighted TED remained unsatisfactory. In this work, we close this gap and give an algorithm for unweighted TED that runs in Õ( n 3+ω/2 ) time.

SODA Conference 2025 Conference Paper

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

• Tomasz Kociumaka
• Jakob Nogler
• Philip Wellnitz

STOC Conference 2024 Conference Paper

On the Communication Complexity of Approximate Pattern Matching

• Tomasz Kociumaka
• Jakob Nogler
• Philip Wellnitz

The decades-old Pattern Matching with Edits problem, given a length- n string T (the text), a length- m string P (the pattern), and a positive integer k (the threshold), asks to list all fragments of T that are at edit distance at most k from P . The one-way communication complexity of this problem is the minimum amount of space needed to encode the answer so that it can be retrieved without accessing the input strings P and T . The closely related Pattern Matching with Mismatches problem (defined in terms of the Hamming distance instead of the edit distance) is already well understood from the communication complexity perspective: Clifford, Kociumaka, and Porat [SODA 2019] proved that Ω( n / m · k log( m / k )) bits are necessary and O ( n / m · k log( m |Σ|/ k )) bits are sufficient; the upper bound allows encoding not only the occurrences of P in T with at most k mismatches but also the substitutions needed to make each k -mismatch occurrence exact. Despite recent improvements in the running time [Charalampopoulos, Kociumaka, and Wellnitz; FOCS 2020 and 2022], the communication complexity of Pattern Matching with Edits remained unexplored, with a lower bound of Ω( n / m · k log( m / k )) bits and an upper bound of O ( n / m · k 3 log m ) bits stemming from previous research. In this work, we prove an upper bound of O ( n / m · k log 2 m ) bits, thus establishing the optimal communication complexity up to logarithmic factors. We also show that O ( n / m · k log m log( m |Σ|)) bits allow encoding, for each k -error occurrence of P in T , the shortest sequence of edits needed to make the occurrence exact. Our result further emphasizes the close relationship between Pattern Matching with Mismatches and Pattern Matching with Edits. We leverage the techniques behind our new result on the communication complexity to obtain quantum algorithms for Pattern Matching with Edits: we demonstrate a quantum algorithm that uses O ( n 1+ o (1) / m · √ km ) queries and O ( n 1+ o (1) / m · (√ k m + k 3.5 )) quantum time. Moreover, when determining the existence of at least one occurrence, the algorithm uses O (√ n 1+ o (1) / m · √ km ) queries and O (√ n 1+ o (1) / m · (√ k m + k 3.5 )) time. For both cases, we establish corresponding lower bounds to demonstrate that the query complexity is optimal up to sub-polynomial factors.

SODA Conference 2023 Conference Paper

Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching

• Ce Jin 0001
• Jakob Nogler

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length- n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood. We show that the complexity of LCS with threshold d smoothly interpolates between the two extreme cases up to n o (1) factors: • LCS with threshold d has a quantum algorithm in n 2/3 +o(1) / d 1/6 query complexity and time complexity, and requires at least Ω( n 2/3 / d 1/6 ) quantum query complexity. Our result improves upon previous upper bounds Õ (min{ n / d 1/2, n 2/3 }) (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples n /τ 1− o (1) synchronizing positions in the string depending on their length-Θ(τ) contexts, and each synchronizing position can be reported by a quantum algorithm in Õ(τ 1/2+ o (1) ) time. Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting. As another application of our quantum string synchronizing set, we study the k-mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most k Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain: • k -mismatch matching has a quantum algorithm with k 3/4 n 1/2+ o (1) query complexity and Õ ( kn 1/2 ) time complexity. We also observe a non-matching quantum query lower bound of.