Christopher Ye 0001

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

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More

• Barna Saha
• Virginia Vassilevska Williams
• Yinzhan Xu
• Christopher Ye 0001

SODA Conference 2024 Conference Paper

Faster Approximate All Pairs Shortest Paths

• Barna Saha
• Christopher Ye 0001

The all pairs shortest path problem (APSP) is one of the foundational problems in computer science. For weighted dense graphs on n vertices, no truly sub-cubic algorithms exist to compute APSP exactly even for undirected graphs. This is popularly known as the APSP conjecture and has played a prominent role in developing the field of fine-grained complexity. The seminal results of Seidel and Zwick show that using fast matrix multiplication (FMM) it is possible to compute APSP on unweighted undirected graphs exactly in Õ ( n ω ) time, and can be approximated within (1 + ɛ ) factor in weighted undirected graphs in time Õ( n ω ) respectively. Here ω is the exponent of FMM, which currently stands at ω = 2. 37188. Moreover even for unweighted undirected graphs, it is not possible to obtain a (2 — ɛ )-multiplicative approximation of APSP for any ɛ > 0 in o ( n ω ) time. Since 2000, a result by Dor, Halperin, and Zwick gave the best 2 approximation algorithm for APSP in unweighted undirected graphs in time Õ( n 7/3 ). This result was recently improved by Deng, Kirkpatrick, Rong, Williams and Zhong to Õ( n 2. 2593 ) using fast min-plus product for bounded-difference matrices which uses FMM as a subroutine (the stated bound here uses new results for computing such min-plus products by Durr). In fact both these results obtain a +2-additive approximation. Recently, Roditty (STOC, 2023) improved the previous bounds for multiplicative 2-approximation of APSP in unweighted undirected graphs giving the best known bound of Õ ( n 2. 25 ). All these algorithms are deterministic. Roditty also considers estimating shortest paths for all paths of length ≥ k for k ≥ 4, and gives improved bounds when the underlying graph is sparse using randomization. Though for dense graphs, the best known bounds still remained at those provided by Dor et al. more than two decades back. In this paper, we provide a multitude of new results for multiplicative and additive approximations of APSP in undirected graphs for both unweighted and weighted cases. We provide new algorithms for multiplicative 2-approximation of unweighted graphs: a deterministic one that runs in Õ ( n 2. 072 ) time and a randomized one that runs in Õ ( n 2. 0318 ) on expectation improving upon the best known bound of Õ ( n 2. 25 ). The algorithm uses FMM as well as new combinatorial insights. For 2-approximating paths of length ≥ k, k ≥ 4, we provide the first improvement after Dor et al. for dense graphs even just using combinatorial methods, and then improve it further using FMM. We next consider additive approximations, and provide improved bounds for all additive β -approximations, β ≥ 4. For example, we achieve a running time of Õ ( n 2. 155 ) for +4 additive approximation improving over the previously known bound of Õ ( n 2. 2 ), and for a +6 additive approximation, our algorithm has a running time of Õ ( n 2. 103 ) as opposed to the Õ ( n 2. 125 ) time that was previously known. For weighted graphs, we show that by allowing small additive errors along with an (1 + ɛ )-multiplicative approximation, it is possible to improve upon Zwick's Õ ( n ω ) algorithm. For example, it is possible to obtain a bi-criteria (1 + ɛ, 2 w u, v ) approximation in Õ ( n 2. 152 ) time for the shortest path distance between all vertex pairs u, v where w u, v is the highest weight edge on the u-v shortest path. Additionally, we provide a landscape of such bi-criteria approximations for weighted and unweighted graphs. Our results point out the crucial role that FMM can play even on approximating APSP on unweighted undirected graphs, and reveal new bottlenecks towards achieving a quadratic running time to approximate APSP.

ICML Conference 2024 Conference Paper

I/O Complexity of Attention, or How Optimal is FlashAttention?

• Barna Saha
• Christopher Ye 0001

Attention is at the heart of the popular Transformer architecture, yet suffers from quadratic time and memory complexity. In a recent significant development, FlashAttention shows that the I/O complexity of attention is the true bottleneck in scaling Transformers. Given two levels of memory hierarchy, a fast cache (e. g. GPU on-chip SRAM) where computation happens and a slow memory (e. g. GPU high-bandwidth memory) where the data resides, the I/O complexity measures the number of accesses to the slow memory. FlashAttention is an I/O-aware algorithm for self-attention that requires $\frac{N^2d^2}{M}$ I/O operations where $N$ is the dimension of the attention matrix, $d$ is the head-dimension and $M$ is the size of cache. Naturally, to further reduce the computational costs of Attention, the authors ask the question: is FlashAttention’s I/O complexity optimal for every value of $M$? We resolve the above question in its full generality by showing an I/O complexity lower bound that matches the upper bound provided by FlashAttention for any values of $M \geq d^2$ within any constant factors. Moreover, our lower bounds do not rely on using combinatorial matrix multiplication for computing the attention matrix: even if one uses fast matrix multiplication, the above I/O complexity bounds cannot be improved. Further, we give a better algorithm with lower I/O complexity for $M < d^2$, and show that it is optimal for combinatorial algorithms. We do so by introducing a new communication complexity protocol for matrix compression, and connecting communication complexity to I/O complexity. We believe this connection could be of independent interest and will find more applications in proving I/O complexity lower bounds in future.

FOCS Conference 2024 Conference Paper

Replicability in High Dimensional Statistics

• Max Hopkins
• Russell Impagliazzo
• Daniel M. Kane
• Sihan Liu
• Christopher Ye 0001

The replicability crisis is a major issue across nearly all areas of empirical science, calling for the formal study of replicability in statistics. Motivated in this context, [Impagliazzo, Lei, Pitassi, and Sorrell STOC 2022] introduced the notion of replicable learning algorithms, and gave basic procedures for 1-dimensional tasks including statistical queries. In this work, we study the computational and statistical cost of replicability for several fundamental high dimensional statistical tasks, including multi-hypothesis testing and mean estimation. Our main contribution establishes a computational and statistical equivalence between optimal replicable algorithms and high dimensional isoperimetric tilings. As a consequence, we obtain matching sample complexity upper and lower bounds for replicable mean estimation of distributions with bounded covariance, resolving an open problem of [Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sivakumar, and Sorrell, STOC 2023] and for the $N$ -Coin Problem, resolving a problem of [Karbasi, Velegkas, Yang, and Zhou, NeurIPS 2023] up to log factors. While our equivalence is computational, allowing us to shave $\log$ factors in sample complexity from the best known efficient algorithms, efficient isoperimetric tilings are not known. To circumvent this, we introduce several relaxed paradigms that do allow for sample and computationally efficient algorithms, including allowing pre-processing, adaptivity, and approximate replicability. In these cases we give efficient algorithms matching or beating the best known sample complexity for mean estimation and the coin problem, including a generic procedure that reduces the standard quadratic overhead of replicability to linear in expectation.