ALT We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported. Under the combinatorial Boolean matrix multiplication conjecture, any subquadratic-time algorithm for this problem must use algebraic techniques. All prior work uses the polynomial matrix inverse as its algebraic tool, but within subquadratic time, this technique can only maintain distances up to a small-polynomial hop bound. So larger distances must be reassembled from short-range pieces by a combinatorial layer. This hybrid algebraic-combinatorial construction has led to a substantial slowdown for dynamic distances compared to other dynamic graph problems relying on algebraic techniques. We give the first subquadratic-time dynamic distance algorithm built on dynamically maintaining a different algebraic object than the matrix inverse. By maintaining the Frobenius form A=KCK⁻¹ of a dynami

ALT We study weighted edit distance between two strings of total length n, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an O(nᵟ)-approximation with Õ(n²⁻ᵟ) running time for every fixed 0 < δ < 1. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every 0 < ε ≤ 1, our randomized algorithm runs in Õ(n⁷/⁴/ε⁸) time and returns a (3+ε)-approximation with probability at least 1-n⁻¹⁰. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.

ALT The classical Weisfeiler-Leman algorithm (also known as the 2-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph isomorphism problem. However, it has also numerous connections to other areas such as algebraic graph theory, logics, proof complexity, combinatorial optimization and machine learning. We prove that the classical Weisfeiler-Leman algorithm terminates after 5(n-1) iterations. This improves over the previous best upper bound of O(n log n) by Lichter, Ponomarenko and Schweitzer [LICS 2019], and asymptotically matches the known lower bound of Ω(n) by Fürer [ICALP 2001]. Additionally, building on our results for the 2-dimensional case, we obtain an improved upper bound of O(nᵏ⁻¹/(k-2)! + nᵏ⁻²) on the number of iterations performed by the k-dimensional Weisfeiler-Leman algorithm, for every k ≥ 3. Our arguments actually hold for a larger class of sequences of colorings of k-tuples; in this larger cla