Workshop Details

Consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights. We solve this problem in $m^{1+o(1)}$ time by refining the shortcutting approach introduced by Li, Li, Rao, and Zhang (STOC 2026).

One of the most basic questions about finding patterns in data is the Induced Subgraph Detection problem. In this problem, we are given a small pattern graph and a large host graph, and are tasked with determining if the host contains the pattern as an induced subgraph. A dream goal of fine-grained complexity is to fully classify those patterns for which Induced Subgraph Detection is easy to solve, and those for which it becomes difficult. In this talk, we present some recent, surprising progress on this classification question, centered around a particularly suspicious pattern known as the 4-cycle.

We will survey the "forbidden structure method," a recently-popular technique for building graph metric sparsifiers. In this method, one uses a simple greedy algorithm to construct a sparsifier, and then shows that the resulting sparsifier does not contain a certain substructure.  Then, one applies bounds from extremal combinatorics to control the maximum possible size of a graph avoiding this structure. We will demonstrate this method on spanners, preservers, shortcut sets, and hopsets as our main sparsifiers of interest.

I will talk about the recently defined notion of a "DAG cover". It is a directed analog of a tree cover, which is closely related to a probabilistic tree embedding. A DAG cover of a general directed graph G is a small collection of DAGs so that for all pairs of vertices s,t in G, some DAG in the collection provides low distortion for dist(s,t). This talk will survey the known results on DAG covers and its variants, with a focus on posing open problems.

Parameterized algorithms are typically studied through
running times of the form (f(k)n^{O(1)}). However, this notation hides
an important tradeoff between the dependence on the parameter (k) and
the dependence on the input size (n). An algorithm with a better
dependence on (k) may have a worse polynomial dependence on (n), and
vice versa. Thus, rather than searching for a single best algorithm,
it is natural to study the Pareto frontier of achievable running
times.

In the first part of the talk, I will discuss several recent successes
in moving this frontier. I will survey some of the main techniques
that have led to linear, near-linear, and almost-linear
fixed-parameter algorithms, as well as algorithms in which the cost of
reading the input is separated additively from the parameter-dependent
computation.

In the second part, I will discuss potential frontiers and barriers in
this paradigm. Which problems should admit substantially better
tradeoffs, but currently lack the necessary techniques? Which problems
should not admit near-linear FPT algorithms, even though we do not yet
have suitable hardness results? I will conclude with some open
questions toward understanding the full landscape of achievable and
impossible tradeoffs.

The conjecture that truly subcubic All-Pairs Shortest-Paths (APSP) algorithms do not exist is central in Fine-Grained Complexity and allows us to explain the hardness of dozens of other important problems. Put differently, the algorithmic research on a large class of problem must be halted until a truly subcubic algorithm for APSP is found. 

This talk will discuss some attempts to refute the APSP conjecture, inspired by recent results breaking the longstanding cubic barrier for the All-Pairs Max-Flow problem.

Sublinear-time graph algorithms have been the subject of numerous studies over the last two decades, and many upper and lower bounds have been developed for them. Despite this, nearly all the existing lower bounds for these algorithms follow from ad hoc approaches that are highly specific to the problem at hand. In this talk, I will propose a systematic way of proving these lower bounds via a method that we call “Markov Chains with Rewinding”.

In this setting, an algorithm is tasked to identify the initial state of a partially observable Markov chain. Unlike traditional Markov chains, we allow “rewinding”. Namely, instead of passive observations, we allow the algorithm that interacts with the Markov chain to rewind back to any previously observed state at any time. I will show how this problem concisely models many of the recent developments on sublinear-time lower bounds for graph problems. I will then describe tools and techniques to reason about markov chains with rewinding, and mention a few open problems and directions.

Based on joint work with Amir Azarmehr, Alma Ghafari, and Madhu Sudan (2026).

The All-Pairs Shortest Paths (APSP) problem is to compute all pairs of distances in a given weighted graph, and the associated *APSP Hypothesis* states that the APSP cannot be solved in subcubic time. Two increasingly stronger assumptions are the *Strong APSP Hypothesis* and the *Directed Unweighted APSP Hypothesis* which state that the fastest-known APSP algorithms on graphs with small weights and unweighted graphs, respectively, are best-possible. In this talk we discuss a surprising connection between these three regimes (unweighted, small weights, polynomially bounded weights): There is an efficient universe reduction for APSP, implying that the three hypotheses are actually equivalent, conditioned on $omega = 2$ and a plausible additive combinatorics assumption. The proof technique is centered around novel rank measure, called the *select-plus rank* of a matrix, and leads to many interesting other results, including some long-awaited APSP-based lower bounds. (Based on this paper: https://arxiv.org/abs/2603.27736)

This talk presents some recent fine-grained complexity results on subgraph finding and extensions to database theory. Specifically, we discuss listing and enumeration algorithms for a fixed pattern graph, with or without projections, in a given host graph. We also discuss generalizations of these problems to hypergraphs, known as join queries or conjunctive queries in database theory.

We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering an outstanding open question in graph streaming literature since the introduction of the model over two decades ago.

Our proof consists of two parts: 

1. Blueprint framework: reducing the problem of proving lower bounds for semi-streaming matching to constructing certain combinatorial objects which we call blueprints; and, 

2. Blueprint construction: an optimal construction of such blueprints usable within this framework. 

Putting these two parts together then implies our semi-streaming matching lower bound.

Based on joint work with Max Jiang and Mars Xiang in https://arxiv.org/pdf/2607.14644 (STOC 2026) and https://arxiv.org/abs/2607.14656 (arXiv; July 2026)

I'll survey our recent series of work (with Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng [FOCS'25, SoCG'26, ICALP'26]) on the fine-grained complexity of computing the diameter of geometric intersection graphs.  Results include the first truly subquadratic-time algorithm for 2D unit disk graphs, as well as near-quadratic conditional lower bounds for 2D line segments, 3D unit balls, etc. even when the diameter is bounded by a small constant.

All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to compute a minimum s,t-cut for every pair of vertices s,t. Recent progress on sequential algorithms for APMC relies on reducing the problem to a small number of exact max-flow computations.

I will present a different approach that yields new algorithms for APMC in unweighted graphs across three computational models: the cut-query model, the streaming model, and the fully dynamic model. These algorithms improve over the previous bounds in these models even for the simpler (single-pair) minimum s,t-cut problem. Our main technical contribution is a new APMC sparsifier constructed using approximate, rather than exact, max-flow computations.

Based on joint work with Yotam Kenneth-Mordoch, with the main results taken from our STOC 2026 paper, but placed in a broader context that includes our ESA 2025 and SODA 2026 papers. 

Conventional wisdom states that the known approximation algorithms for k-Center are optimal. We show that with a small additive error, one can circumvent this belief and provide fast, better than 2-approximation algorithms. We also note that there is still some fine-grained hardness here. The talk will mostly focus on the algorithmic improvements.

Roundtrip spanners are the analog of spanners in directed graphs, where the roundtrip metric is used as a notion of distance. Recent works have shown existential results of roundtrip spanners nearly matching the undirected case, but the time complexity for constructing roundtrip spanners is still widely open. I will talk about faster algorithms for roundtrip spanners and related problems including roundtrip emulators and girth approximation.

This is a joint work with Alina Harbuzova, Virginia Vassilevska Williams and Zixuan Xu, which appeared in SODA 2024. Link: https://arxiv.org/abs/2310.20473