We consider the classic 3SUM problem: given sets of integers A, B, C, determine whether there is a tuple (a, b, c) ∈ A × B × C satisfying a + b = c. The 3SUM Hypothesis, central in fine-grained complexity, states that there does not exist a truly subquadratic time 3SUM algorithm. Given this long-standing barrier, recent work over the past decade has explored 3SUM from a data structural perspective. Specifically, in the 3SUM in preprocessed universes regime, we are tasked with preprocessing sets A, B of size n, to create a space-efficient data structure that can quickly answer queries, each of which is a 3SUM problem of the form A', B', C', where A' ⊆ A and B' ⊆ B. A series of results have achieved Õ(n²) preprocessing time, Õ(n²) space, and query time improving progressively from Õ(n^{1.9}) [Timothy M. Chan and Moshe Lewenstein, 2015] to Õ(n^{11/6}) [Timothy M. Chan et al., 2023] to Õ(n^{1.5}) [Kasliwal et al., 2025]. Given these series of works improving query time, a natural open question has emerged: can one achieve both truly subquadratic space and truly subquadratic query time for 3SUM in preprocessed universes? We resolve this question affirmatively, presenting a tradeoff curve between query and space complexity. Specifically, we present a simple randomized algorithm achieving Õ(n^{1.5 + ε}) query time and Õ(n^{2 - 2ε/3}) space complexity. Furthermore, our algorithm has Õ(n²) preprocessing time, matching past work. Notably, quadratic preprocessing is likely necessary for our tradeoff as either the preprocessing or the query time must be at least n^{2-o(1)} under the 3SUM Hypothesis.

Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard problem. As computing the exact diameter in m-edge graphs requires m^{2-o(1)} time under the Strong Exponential Time Hypothesis, much work has gone into approximating this parameter. Recent work has achieved a full conditional lower bound tradeoff curve for both directed and undirected graphs [Dalirrooyfard, Li and Vassilevska W., FOCS'21]. However, the best known upper bounds do not match the lower bounds. In particular, the best known approximation scheme for undirected graph diameter [Cairo-Grossi-Rizzi, SODA 2016] has not been improved. Moreover, this scheme is randomized and no similar deterministic scheme is known. Another fundamental field of research in shortest paths computation is the construction of approximate distance oracles. Thorup and Zwick [JACM'05] provided the first such distance oracle with constant query time and (conditionally) optimal space, and in the years since many advances have led to a vast toolbox of techniques and data structures. These two areas of research seem natural to combine since they both concern approximating shortest paths. However, the known diameter approximation algorithms only use a small subset of the techniques used in distance oracles research. In this work we show that in fact approximate diameter and distance oracles are intricately connected. We first demonstrate a strong connection between the current best known diameter approximation scheme of Cairo, Grossi and Rizzi ("CGR") and the (2k-1)-approximate distance oracle of Thorup and Zwick. This allows us to derandomize the CGR algorithm and obtain the first deterministic diameter approximation tradeoff. We further derandomize other central techniques in the field of distance oracles and use them to achieve new deterministic diameter approximation algorithms, including a simpler 3/2-approximation with no additive error and a new 5/3-approximation, the first new step in the diameter approximation tradeoff in almost a decade. Finally, we show how these new techniques can be used to derandomize many current best known results in various fields of shortest paths approximations.

The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, beginning with the work of Dor, Halperin and Zwick [SICOMP’01]. Many recent works have attempted to improve these original algorithms using the algebraic tools of fast matrix multiplication. We improve on these results for the following problems.

In this work we study shortest path problems in multimode graphs, a generalization of the min-distance measure introduced by Abboud, Vassilevska W. and Wang in [SODA'16]. A multimode shortest path is the shortest path using one of multiple "modes" of transportation that cannot be combined. This represents real-world scenarios where different modes are not combinable, such as flights operated by different airline alliances. The problem arises naturally in machine learning in the context of learning with multiple embedding. More precisely, a k-multimode graph is a collection of k graphs on the same vertex set and the k-mode distance between two vertices is defined as the minimum among the distances computed in each individual graph. We focus on approximating fundamental graph parameters on these graphs, specifically diameter and radius. In undirected multimode graphs we first show an elegant linear time 3-approximation algorithm for 2-mode diameter. We then extend this idea into a general subroutine that can be used as a part of any α-approximation, and use it to construct a 2 and 2.5 approximation algorithm for 2-mode diameter. For undirected radius, we introduce a general scheme that can compute a 3-approximation of the k-mode radius for any k and runs in near linear time in the case of k = O(1). In the directed case we establish an equivalence between approximating 2-mode diameter on DAGs and approximating the min-diameter, while for general graphs we develop novel techniques and provide a linear time algorithm to determine whether the diameter is finite. We also develop many conditional fine-grained lower bounds for various multimode diameter and radius approximation problems. We are able to show that many of our algorithms are tight under popular fine-grained complexity hypotheses, including our linear time 3-approximation for 3-mode undirected diameter and radius. As part of this effort we propose the first extension to the Hitting Set Hypothesis [SODA'16], which we call the 𝓁-Hitting Set Hypothesis. We use this hypothesis to prove the first parameterized lower bound tradeoff for radius approximation algorithms.

We consider the classical k-Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even (2 + ε )-approximation algorithms for every ε > 0 running in near-linear time. The conventional wisdom is that the problem is closed, as (2 — ε )-approximation is NP-hard when k is part of the input, and for constant k ≥ 2 it requires nk-o(1) time under the Strong Exponential Time Hypothesis (SETH).

Inspired by artistic practices such as beadwork and himmeli, we study the problem of threading a single string through a set of tubes, so that pulling the string forms a desired graph. More precisely, given a connected graph (where edges represent tubes and vertices represent junctions where they meet), we give a polynomial-time algorithm to find a minimum-length closed walk (representing a threading of string) that induces a connected graph of string at every junction. The algorithm is based on a surprising reduction to minimum-weight perfect matching. Along the way, we give tight worst-case bounds on the length of the optimal threading and on the maximum number of times this threading can visit a single edge. We also give more efficient solutions to two special cases: cubic graphs and the case when each edge can be visited at most twice.

In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for 2-approximate APSP in Õ(n2.5-r + nω(r)) time, for any r ∈ [0,1]. This is O(n2.032) time, using known bounds for rectangular matrix multiplication nω(r) [Le Gall, Urrutia, SODA 2018]. Our result improves on the Õ(n2·25) bound of [Roditty, STOC 2023], and on the bound of [Baswana, Kavitha, SICOMP 2010] for graphs with m ≥ n1·532 edges.