Sixteen papers by CSE researchers at SODA 2025

CSE researchers are presenting a total of 16 papers at the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA), one of the top international conferences in the field of theoretical computer science. Taking place in New Orleans, LA, from January 12-15, SODA brings together leading mathematicians, computer scientists, and more to share the latest research related to the design and analysis of efficient algorithms and data structures for discrete problems.

With 16 total papers at this year’s conference, more than any other institution represented at the event, University of Michigan researchers are bringing a host of new findings and innovations to the field. Their papers cover a range of topics related to discrete algorithms and theoretical computer science, including graph algorithms, optimization techniques, and computational complexity.

The papers being presented are as follows, with the names of authors affiliated with CSE in bold:

A Lower Bound for Light Spanners in General Graphs
Greg Bodwin, Jeremy Flics

Abstract: A recent upper bound by Le and Solomon [STOC ’23] has established that every n-node graph has a (1+ε)(2k−1)-spanner with lightness O(ε⁻¹n^1/k). This bound is optimal up to its dependence on ε; the remaining open problem is whether this dependence can be improved or perhaps even removed entirely. We show that the ε-dependence cannot in fact be completely removed. For constant k and for ε:=Θ(n^−1/2k−1), we show a lower bound on lightness of Ω(ε^−1/kn^1/k).For example, this implies that there are graphs for which any 3-spanner has lightness Ω(n^2/3), improving on the previous lower bound of Ω(n^1/2). An unusual feature of our lower bound is that it is conditional on the girth conjecture with parameter k−1 rather than k. We additionally show that this implies certain technical limitations to improving our lower bound further. In particular, under the same conditional, generalizing our lower bound to all ε or obtaining an optimal ε-dependence are as hard as proving the girth conjecture for all constant k.

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
Yaowei Long, Seth Pettie, Thatchaphol Saranurak

Abstract: We consider the problem of assigning short labels to the vertices and edges of a graph G so that given any query ⟨s,t,F⟩ with |F|≤f, we can determine whether s and t are still connected in G−F, given only the labels of F∪{s,t}. This problem has been considered when F⊂E (edge faults), where correctness is guaranteed with high probability (w.h.p.) or deterministically, and when F⊂V (vertex faults), both w.h.p.~and deterministically. Our main results are as follows.

[Deterministic Edge Faults.] We give a new deterministic labeling scheme for edge faults that uses Õ(√f)-bit labels, which can be constructed in polynomial time. This improves on Dory and Parter’s [PODC 2021] existential bound of O(f log n) (requiring exponential time to compute) and the efficient Õ(f²)-bit scheme of Izumi, Emek, Wadayama, and Masuzawa [PODC 2023]. Our construction uses an improved edge-expander hierarchy and a distributed coding technique based on Reed-Solomon codes.

[Deterministic Vertex Faults.] We improve Parter, Petruschka, and Pettie’s [STOC 2024] deterministic O(f⁷log¹³n)-bit labeling scheme for vertex faults to O(f⁴log^7.5n) bits, using an improved vertex-expander hierarchy and better sparsification of shortcut graphs.

[Randomized Edge/Vertex Faults.] We improve the size of Dory and Parter’s [PODC 2021] randomized edge fault labeling scheme from O(min{f+log n,log³n}) bits to O(min{f+log n,log²n log f}) bits, shaving a log n/log f factor. We also improve the size of Parter, Petruschka, and Pettie’s [STOC 2024] randomized vertex fault labeling scheme from O(f³log⁵n) bits to O(f²log⁶n) bits, which comes closer to their Ω(f)-bit lower bound.

Universal Perfect Samplers for Incremental Streams
Seth Pettie, Dingyu Wang

Abstract: If G:ℝ₊→ℝ₊, the G-moment of a vector x∈ℝⁿ₊ is G(x)=∑_v∈[n]G(x(v)) and the G-sampling problem is to select an index v∗∈[n] according to its contribution to the G-moment, i.e., such that P(v_∗=v)=G(x(v))/G(x). Approximate G-samplers may introduce multiplicative and/or additive errors to this probability, and some have a non-trivial probability of failure.

In this paper we focus on the exact G-sampling problem, where G is selected from the class □ of Laplace exponents of non-negative, one-dimensional Lévy processes, which includes several well studied classes such as pth moments G(z)=z^p, p∈[0,1], logarithms G(z)=log(1+z), Cohen and Geri’s soft concave sublinear functions, which are used to approximate concave sublinear functions, including cap statistics. We develop G-samplers for a vector x∈ℝⁿ₊ that is presented as an incremental stream of positive updates. In particular:

* For any G∈□, we give a very simple G-sampler that uses 2 words of memory and stores at all times a v∗∈[n], such that Pr(v∗=v) is exactly G(x(v))/G(x).

* We give a “universal” □-sampler that uses O(log n) words of memory w.h.p., and given any G∈ at query time, produces an exact G-sample.

With an overhead of a factor of k, both samplers can be used to G-sample a sequence of k indices with or without replacement. Our sampling framework is simple and versatile, and can easily be generalized to sampling from more complex objects like graphs and hypergraphs.

Min-CSPs on Complete Instances
Aditya Anand, Euiwoong Lee, Amatya Sharma

Abstract: Given a fixed arity k≥2, Min-k-CSP on complete instances involves a set of n variables V and one nontrivial constraint for every k-subset of variables (so there are (ⁿ_k) constraints). The goal is to find an assignment that minimizes unsatisfied constraints. Unlike Max-k-CSP that admits a PTAS on dense or expanding instances, the approximability of Min-k-CSP is less understood. For some CSPs like Min-k-SAT, there’s an approximation-preserving reduction from general to dense instances, making complete instances unique for potential new techniques.

This paper initiates a study of Min-k-CSPs on complete instances. We present an O(1)-approximation algorithm for Min-2-SAT on complete instances, the minimization version of Max-2-SAT. Since O(1)-approximation on dense or expanding instances refutes the Unique Games Conjecture, it shows a strict separation between complete and dense/expanding instances.

Then we study the decision versions of CSPs, aiming to satisfy all constraints; which is necessary for any nontrivial approximation. Our second main result is a quasi-polynomial time algorithm for every Boolean k-CSP on complete instances, including k-SAT. We provide additional algorithmic and hardness results for CSPs with larger alphabets, characterizing (arity, alphabet size) pairs that admit a quasi-polynomial time algorithm on complete instances.

Unbreakable Decomposition in Close-to-Linear Time
Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, Thatchaphol Saranurak

Abstract: Unbreakable decomposition, introduced by Cygan et al. (SICOMP ’19) and Cygan et al. (TALG ’20), has proven to be one of the most powerful tools for parameterized graph cut problems in recent years. Unfortunately, all known constructions require at least Ω_k(mn²) time, given an undirected graph with n vertices, m edges, and cut-size parameter k. In this work, we show the first close-to-linear time parameterized algorithm that computes an unbreakable decomposition. More precisely, for any 0<ϵ≤1, our algorithm runs in time 2^{O(k/ϵ log k/ϵ)}m^1+ϵ and computes a (O(k/ϵ),k) unbreakable tree decomposition of G, where each bag has adhesion at most O(k/ϵ).

This immediately opens up possibilities for obtaining close-to-linear time algorithms for numerous problems whose only known solution is based on unbreakable decomposition.

Improved Online Reachability Preservers
Greg Bodwin, Tuong Le

Abstract: A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an n-node directed input graph G among a set of given demand pairs P of size |P|=p. We give constructions of sparse reachability preservers in the online setting, where G is given on input, the demand pairs (s,t)∈P arrive one at a time, and we must irrevocably add edges to a preserver H to ensure reachability for the pair (s,t) before we can see the next demand pair. Our main results are:

— There is a construction that guarantees a maximum preserver size of

|E(H) ≤ O (n^0.72p^0.56 + n^0.6p^0.7 + n).

This improves polynomially on the previous online upper bound of O(min{np^0.5, n^0.5p}) + n, implicit in the work of Coppersmith and Elkin [SODA ’05].

— Given a promise that the demand pairs will satisfy P⊆S×V for some vertex set S of size |S|=:σ, there is a construction that guarantees a maximum preserver size of

|E(H)| ≤ O ((npσ)^1/2 + n).

A slightly different construction gives the same result for the setting P⊆V×S. This improves polynomially on the previous online upper bound of O(σn) (folklore).

All of these constructions are polynomial time, deterministic, and they do not require knowledge of the values of p,σ, or S. Our techniques also give a small polynomial improvement in the current upper bounds for offline reachability preservers, and they extend to a stronger model in which we must commit to a path for all possible reachable pairs in G before any demand pairs have been received. As an application, we improve the competitive ratio for Online Unweighted Directed Steiner Forest to O(n^3/5+ε).

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
Michał Dereziński, Christopher Musco, Jiaming Yang

Abstract: We present a new class of preconditioned iterative methods for solving linear systems of the form Ax=b. Our methods are based on constructing a low-rank Nyström approximation to A using sparse random sketching. This approximation is used to construct a preconditioner, which itself is inverted quickly using additional levels of random sketching and preconditioning. We prove that the convergence of our methods depends on a natural average condition number of A, which improves as the rank of the Nyström approximation increases. Concretely, this allows us to obtain faster runtimes for a number of fundamental linear algebraic problems:

1. We show how to solve any n×n linear system that is well-conditioned except for k outlying large singular values in Õ (n^2.065+k^ω) time, improving on a recent result of [Dereziński, Yang, STOC 2024] for all k≳n0.78.

2. We give the first Õ(n²+d_λ^ω) time algorithm for solving a regularized linear system (A+λI)x=b, where A is positive semidefinite with effective dimension d_λ. This problem arises in applications like Gaussian process regression.

3. We give faster algorithms for approximating Schatten p-norms and other matrix norms. For example, for the Schatten 1 (nuclear) norm, we give an algorithm that runs in Õ(n^2.11) time, improving on an Õ(n^2.18) method of [Musco et al., ITCS 2018].

Interestingly, previous state-of-the-art algorithms for most of the problems above relied on stochastic iterative methods, like stochastic coordinate and gradient descent. Our work takes a completely different approach, instead leveraging tools from matrix sketching.

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
Aditya Anand, Thatchaphol Saranurak, Yunfan Wang

Abstract: We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an n-vertex graph G, our algorithm makes Õ(n^5/3) queries to compute the global min-cut in G. As a key ingredient, we also show an algorithm for finding s-t max-flows of size Õ(n) in Õ(n^5/3) queries. We also show efficient cut-query implementations of versions of expander decomposition and isolating cuts, which may be of independent interest.

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
Lily Wang, Greg Bodwin

Abstract: The restoration lemma is a classic result by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [PODC ’01], which relates the structure of shortest paths in a graph G before and after some edges in the graph fail. Their work shows that, after one edge failure, any replacement shortest path avoiding this failing edge can be partitioned into two pre-failure shortest paths. More generally, this implies an additive tradeoff between fault tolerance and subpath count: for any f,k, we can partition any f-edge-failure replacement shortest path into k+1 subpaths which are each an (f−k)-edge-failure replacement shortest path. This generalized result has found applications in routing, graph algorithms, fault tolerant network design, and more.

Our main result improves this to a multiplicative tradeoff between fault tolerance and subpath count. We show that for all f,k, any f-edge-failure replacement path can be partitioned into O(k) subpaths that are each an (f/k)-edge-failure replacement path. We also show an asymptotically matching lower bound. In particular, our results imply that the original restoration lemma is exactly tight in the case k=1, but can be significantly improved for larger k. We also show an extension of this result to weighted input graphs, and we give efficient algorithms that compute path decompositions satisfying our improved restoration lemmas.

Quasi-Monte Carlo Beyond Hardy-Krause
Nikhil Bansal, Haotian Jiang

Abstract: The classical approaches to numerically integrating a function f are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error O(σ(f)/√n), where σ(f) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma-Hlawka inequality, they have error Õ(σ_𝖧𝖪(f)/n), where σ_𝖧𝖪(f) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.

In this work, we give a simple randomized algorithm that produces QMC point sets with the following desirable features: (1) It achieves substantially better error than given by the classical Koksma-Hlawka inequality. In particular, it has error Õ(σ_𝖲𝖮(f)/n), where σ_𝖲𝖮(f) is a new measure of variation that we introduce, which is substantially smaller than the Hardy-Krause variation. (2) The algorithm only requires random samples from the underlying distribution, which makes it as flexible as MC. (3) It automatically achieves the best of both MC and QMC (and the above improvement over Hardy-Krause variation) in an optimal way. (4) The algorithm is extremely efficient, with an amortized Õ(1) runtime per sample.

Our method is based on the classical transference principle in geometric discrepancy, combined with recent algorithmic innovations in combinatorial discrepancy that besides producing low-discrepancy colorings, also guarantee certain subgaussian properties. This allows us to bypass several limitations of previous works in bridging the gap between MC and QMC methods and go beyond the Hardy-Krause variation.

Beyond 2-approximation for k-Center in Graphs
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, Nicole Wein

Abstract: 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 n^k−o(1) time under the Strong Exponential Time Hypothesis (SETH).

Our first set of results show that one can beat the multiplicative factor of 2 in undirected unweighted graphs if one is willing to allow additional small additive error, obtaining (2−ε,O(1)) approximations. We provide several algorithms that achieve such approximations for all integers k with running time O(n^k−δ) for δ>0. For instance, for every k≥2, we obtain an O(mn+n^k/2+1) time (2−1/2k−1,1−1/2k−1)-approximation to k-Center, and for every k≥10 we obtain a (3/2,1/2)-approximation algorithm running in n^{k−1+1/(k+1)+o(1)} time. For 2-Center we also obtain an O~(mn^ω/3) time (5/3,2/3)-approximation algorithm, where ω<2.372 is the fast matrix multiplication exponent. Notably, the running time of this 2-Center algorithm is faster than the time needed to compute APSP.

Our second set of results are strong fine-grained lower bounds for k-Center. We show that our (3/2,O(1))-approximation algorithm is optimal, under SETH, as any (3/2−ε,O(1))-approximation algorithm requires n^k−o(1) time. We also give a time/approximation trade-off: under SETH, for any integer t≥1, n^{k/t2−1−o(1)} time is needed for any (2−1/(2t−1),O(1))-approximation algorithm for k-Center. This explains why our (2−ε,O(1)) approximation algorithms have k appearing in the exponent of the running time. Our reductions also imply that, assuming ETH, the approximation ratio 2 of the known near-linear time algorithms cannot be improved by any algorithm whose running time is a polynomial independent of k, even if one allows additive error.

Unique-neighbor Expanders with Better Expansion for Polynomial-sized Sets
Yeyuan Chen

Abstract: A (d₁,d₂)-biregular bipartite graph G=(L∪R,E) is called left-(m,δ) unique-neighbor expander iff each subset S of the left vertices with |S|≤m has at least δd₁|S| unique-neighbors, where unique-neighbors mean vertices with exactly one neighbor in S. We can also define right/two-sided expanders similarly. In this paper, we give the following three strongly explicit constructions of unique-neighbor expanders with better unique-neighbor expansion for polynomial-sized sets, while sufficient expansion for linear-sized sets is also preserved:

(1) Two-sided (n^1/3−ϵ,1−ϵ) lossless expanders for arbitrary ϵ>0 and aspect ratio.

(2) Left-(Ω(n),1−ϵ) lossless expanders with right-(n^1/3−ϵ,δ) expansion for some δ>0.

(3) Two-sided-(Ω(n),δ) unique-neighbor expanders with two-sided-(n^Ω(1),1/2−ϵ) expansion.

The second construction exhibits the first explicit family of one-sided lossless expanders with unique-neighbor expansion for polynomial-sized sets from the other side and constant aspect ratio. The third construction gives two-sided unique-neighbor expanders with additional (1/2−ϵ) unique-neighbor expansion for two-sided polynomial-sized sets, which approaches the 1/2 requirement in Lin and Hsieh (arXiv:2203.03581).

Our techniques involve tripartite product recently introduced by Hsieh et al (STOC 2024), combined with a generalized existence argument of biregular graph with optimal two-sided unique-neighbor expansion for almost all degrees. We also use a new reduction from large girth/bicycle-freeness to vertex expansion, which might be of independent interest.

New Separations and Reductions for Directed Hopsets and Preservers
Gary Hoppenworth, Yinzhan Xu, Zixuan Xu

Abstract: We study distance preservers, hopsets, and shortcut sets in n-node, m-edge directed graphs, and show improved bounds and new reductions for various settings of these problems. Our first set of results is about exact and approximate distance preservers. We give the following bounds on the size of directed distance preservers with p demand pairs: 1) Õ(n^5/6p^2/3+n) edges for exact distance preservers in unweighted graphs; and 2) Ω(n^2/3p^2/3) edges for approximate distance preservers with any given finite stretch, in graphs with arbitrary aspect ratio.

Additionally, we establish a new directed-to-undirected reduction for exact distance preservers. We show that if undirected distance preservers have size O(nλpμ+n) for constants λ,μ>0, then directed distance preservers have size O(n^1/2−λp^{1+μ−λ/2−λ}+n^1/2p+n). As a consequence of the reduction, if current upper bounds for undirected preservers can be improved for some p≤n, then so can current upper bounds for directed preservers.

Our second set of results is about directed hopsets and shortcut sets. For hopsets in directed graphs, we prove that the hopbound is: 1) Ω(n^2/9) for O(m)-size shortcut sets, improving the previous Ω(n^1/5) bound [Vassilevska Williams, Xu and Xu, SODA 2024]; 2) Ω(n^2/7) for O(m)-size exact hopsets in unweighted graphs, improving the previous Ω(n^1/4) bound [Bodwin and Hoppenworth, FOCS 2023]; and 3) Ω(n^1/2) for O(n)-size approximate hopsets with any given finite stretch, in graphs with arbitrary aspect ratio. This result establishes a separation between this setting and O(n)-size approximate hopsets for graphs with polynomial aspect ratio, which have hopbound Õ(n^1/3) [Bernstein and Wein, SODA 2023].

A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices
Seth Pettie, Gabor Tardos

Abstract: The theory of forbidden 0-1 matrices generalizes Turan-style (bipartite) subgraph avoidance, Davenport-Schinzel theory, and Zarankiewicz-type problems, and has been influential in many areas, such as discrete and computational geometry, the analysis of self-adjusting data structures, and the development of the graph parameter twin width.

The foremost open problems in this area is to resolve the Pach-Tardos conjecture from 2005, which states that if a forbidden pattern P∈{0,1}^k×l is the bipartite incidence matrix of an acyclic graph (forest), then Ex(P,n)=O(nlog^CPn), where C_P is a constant depending only on P. This conjecture has been confirmed on many small patterns, specifically all P with weight at most 5, and all but two with weight 6.

The main result of this paper is a clean refutation of the Pach-Tardos conjecture. Specifically, we prove that Ex(S₀,n),Ex(S₁,n) ≥ n2^Ω(√logn), where S₀,S₁ are the outstanding weight-6 patterns. We also prove sharp bounds on the entire class of alternating patterns (P_t), specifically that for every t≥2, Ex(P_t,n)=Θ(n(log n/log log n)^t). This is the first proof of an asymptotically sharp bound that is ω(n log n).

Parallel Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Abstract: Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph G=(V,E), a near-optimal ϕ-expander decomposition is a partition V₁,V₂,…,V_k of the vertex set V where each subgraph G[Vi] is a ϕ-expander, and only an Õ(ϕ)-fraction of the edges cross between partition sets.

In this article, we give the first near-optimal parallel algorithm to compute ϕ-expander decompositions in near-linear work Õ(m/ϕ²) and near-constant span Õ(1/ϕ⁴). Our algorithm is very simple and likely practical. Our algorithm can also be implemented in the distributed Congest model in Õ(1/ϕ⁴) rounds.

Our results surpass the theoretical guarantees of the current state-of-the-art parallel algorithms [Chang-Saranurak PODC ’19, Chang-Saranurak FOCS ’20], while being the first to ensure that only an Õ(ϕ) fraction of edges cross between partition sets. In contrast, previous algorithms [Chang-Saranurak PODC ’19, Chang-Saranurak FOCS ’20] admit at least an O(ϕ^1/3) fraction of crossing edges, a polynomial loss in quality inherent to their random-walk-based techniques. Our algorithm, instead, leverages flow-based techniques and extends the popular sequential algorithm presented in [Saranurak-Wang SODA ’19].

Eulerian Graph Sparsification by Effective Resistance Decomposition
Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, Yibin Zhao

Abstract: We provide an algorithm that, given an n-vertex m-edge Eulerian graph with polynomially bounded weights, computes an Ŏ(n log² n⋅ε⁻²)-edge ε-approximate Eulerian sparsifier with high probability in Ŏ(m log³ n) time (where Ŏ(⋅) hides polyloglog(n) factors). Due to a reduction from [Peng-Song, STOC ’22], this yields an Ŏ(m log³ n + n log⁶ n)-time algorithm for solving n-vertex m-edge Eulerian Laplacian systems with polynomially-bounded weights with high probability, improving upon the previous state-of-the-art runtime of Ω(m log⁸ n + n log²³ n). We also give a polynomial-time algorithm that computes O(min(n log n ⋅ ε⁻² + n log^5/3 n ⋅ ε^−4/3, n log^3/2 n ⋅ ε⁻²))-edge sparsifiers, improving the best such sparsity bound of O(n log² n ⋅ ε⁻² + n log^8/3 n ⋅ ε^−4/3) [Sachdeva-Thudi-Zhao, ICALP ’24]. Finally, we show that our techniques extend to yield the first O(m⋅polylog(n)) time algorithm for computing O(nε⁻¹⋅polylog(n))-edge graphical spectral sketches, as well as a natural Eulerian generalization we introduce.

In contrast to prior Eulerian graph sparsification algorithms which used either short cycle or expander decompositions, our algorithms use a simple efficient effective resistance decomposition scheme we introduce. Our algorithms apply a natural sampling scheme and electrical routing (to achieve degree balance) to such decompositions. Our analysis leverages new asymmetric variance bounds specialized to Eulerian Laplacians and tools from discrepancy theory.