Papers

Disaggregated LLM inference executes the prefill and decode phases on separate resource pools, reducing interference between the two phases. However, this architecture introduces a coupled scheduling problem because a request that completes prefill retains its prompt KV cache in prefill memory until it is admitted to the decode pool. Prefill and decode admission decisions therefore jointly determine memory occupancy and request completion times. To the best of our knowledge, this problem lacks a formal formulation, and no approximation guarantees are known for request scheduling in disaggregated LLM inference. We formalize this setting as the dual-memory request scheduling (DMRS) problem, whose objective is to minimize the sum of request completion times, and prove that it is strongly NP-hard. We develop two deterministic polynomial-time approximation algorithms. The first applies to instances satisfying $\alpha<1$ and $\beta<1$ and achieves an approximation ratio of $8+\frac{4}{1-\alpha}+\frac{8}{1-\beta}$, where $\alpha$ and $\beta$ are the maximum normalized prefill and peak decode memory demands among all requests, respectively. In particular, it yields a $32$-approximation when $\alpha,\beta\leq 1/2$. The second algorithm applies to all feasible instances and achieves a uniform $36$-approximation. Finally, evaluations on two H100 GPUs using trace-derived offline workloads show that the proposed algorithms reduce the sum of request completion times relative to multiple vLLM deployment baselines.

FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood. We prove that this rule can require $n^{\Omega(1)}$ many colors on certain bipartite graph of $n$ vertices even when the vertices arrive in a uniformly random order. This refutes the conjecture of Bosek, Gutowski, Lasoń, and Przybyło [BGLP24] that FirstFit uses a polylogarithmic expected number of colors on every bipartite graph in the random order model. We obtain the lower bound by analyzing the FirstFit coloring process on random bipartite graphs, where vertices arrive to either side with equal probability, and with an independent edge density $n^{-x}$ for some $0 < x < 1$. Our result can also be viewed as a qualitative strengthening of Kučera [Kuč91], who showed that, for every $\epsilon > 0$, there are graphs with chromatic number at most $n^{\epsilon}$ on which FirstFit uses $\Omega(n/\log n)$ colors in expectation under a uniformly random order. Our result shows that such poor behavior of FirstFit already occurs for $\chi(G) = 2$.

In random order online sorting, a fixed multiset of $n$ real numbers arrives in a uniformly random order. Each value must be placed immediately and irrevocably into an empty position of an array with exactly $n$ positions. The objective is to minimize the sum of the absolute differences between consecutive entries. If the entire input were known in advance, sorting the values would be optimal and would have cost equal to the range of the input. We prove that the optimal worst case competitive ratio in this model is $\Theta(\log n)$ with high probability. In particular, we give a single online algorithm that achieves an $O(\log n)$ competitive ratio with high probability for every fixed input, and we show that every randomized online algorithm has some fixed input on which an $\Omega(\log n)$ ratio is unavoidable with high probability. The same upper bound also holds for independent samples from an arbitrary unknown distribution on the real line. The algorithm uses the random arrival order to learn the relative positions of future values from the values seen so far. It maintains a hierarchy of small regions of the input order and allows an arriving value to use nearby space when its preferred region is full. This flexibility avoids the need to reserve large amounts of space for unlikely local fluctuations. The analysis shows that large displacements become rapidly less likely as their scale grows, leading to the $O(\log n)$ high probability bound. A matching lower bound shows that no randomized online algorithm can improve the logarithmic dependence in the worst case.

Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in $\mathcal{O}^*((2-\varepsilon)^n)$ or $\mathcal{O}^*((2-\varepsilon)^m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. On the other hand, simple exhaustive search and the standard inclusion-exclusion give $\mathcal{O}^*(2^n)$-time and $\mathcal{O}^*(2^m)$-time algorithms, respectively. A natural line of research is to beat these SETH-based barriers for restricted versions, such as #$k$-SAT (where each clause contains at most $k$ literals) or #$d$-occ-SAT (where each variable appears in at most $d$ clauses). It is known that the $2^n$-barrier can be broken when $k$ or $d$ is any constant; yet, whether the $2^m$-barrier can also be broken in these cases remains unknown. We present two simple algorithms that overcome the $2^m$-barrier. First, for #$k$-SAT, we give an $\mathcal{O}^*(2^{m(1-1/O(k))})$-time algorithm, thereby breaking the $2^m$-barrier for any constant $k$. Second, for #$2$-occ-SAT (which also includes the problem of counting the number of edge covers in a graph as a special case), we provide an algorithm with runtime $\mathcal{O}^*(2^{m\omega/3})$, where $\omega < 2.3714$ is the matrix multiplication exponent. Furthermore, we demonstrate that both algorithms generalize to the weighted counting setting while preserving the same runtime bounds. On the hardness side, we present a reduction from #Max-$d$-SAT to #$d$-occ-SAT, showing that for any $d\ge 3$, #$d$-occ-SAT admits no $\mathcal{O}^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, even on positive formulas, under the hypothesis that #Max-3-SAT on $n$ variables admits no $\mathcal{O}^*((2-\varepsilon)^n)$-time algorithm for any such $\varepsilon$.

Suffix arrays over LLM (pre)training corpora underpin deduplication, contamination testing, n-gram statistics, and training-data attribution, and every new corpus or tokenizer needs a new one. GPU constructors are fast but bounded by device memory, and out-of-core pipelines run at CPU speed, reaching trillions of tokens by building sharded indexes. Reach is bounded not by the size of the data but by what must stay resident, and in a partitioned construction that is the coupling between partitions. We present Cascade, which requires none of it to stay resident. Splitter K-grams sampled from the corpus fix every partition's range of the final suffix array before any sorting, so the GPU sorts and ranks partitions independently and never merges them. The partitions are still coupled: every round of the method needs ranks that other partitions hold, classically kept in a global rank array (the inverse suffix array) that must stay resident. We instead send each rank to the one partition that needs it, and maintain an invariant ensuring ranks are only ever compared within one partition, so no global rank array is needed. The text and a compact partition map, the only structures read at random, then stay in host memory by choice rather than necessity, one at a time when memory is short; every other structure becomes a stream that can be placed across device memory, host memory, and disk as it is written. On a single GPU node, Cascade builds exact suffix arrays of up to 238B tokens, 2.4-6.8x faster than infini-gram's pipeline and 5.9-10.9x faster than libsais.

We study a natural greedy algorithm for the Airplane Refueling Problem (ARP), based on a well-known priority rule. We show that this algorithm achieves an approximation guarantee of $9/20$, noticeably improving the previously known $1/12$ guarantee for a fast algorithm. We also show that the same priority rule can be implemented in $O(n\log n)$ time and $O(n)$ space using a dynamic convex-hull data structure. These results provide a worst-case approximation guarantee for an existing greedy priority rule and establish an efficient implementation. In the real-RAM model, the running-time bound is independent of the magnitude of the processing times. The resulting method is also suitable as a fast primal routine inside more complex exact and approximation algorithms for large instances. These results narrow the gap between theoretically strong but complex approximation schemes and lightweight algorithms that can be used directly in computational pipelines. The algorithm combines a simple selection rule with a provable performance bound, making it a useful baseline for further algorithmic studies of ARP.

Nearest-neighbor (NN) search underlies countless robotics algorithms, but many state spaces are not Euclidean: orientations live on $SO(2)$ or $SO(3)$ and poses on $SE(2)$ or $SE(3)$, and a Euclidean KD-tree on their raw coordinates returns wrong neighbors. We present a header-only, dependency-free C++ KD-tree library for exact NN search on user-defined product manifolds declared at compile time: the space is composed from base manifolds ($\mathbb{R}^n$, $SO(2)$, $SO(3)$, $S^n$; products $SE(2)$, $SE(3)$, tori) with a single type alias, and the library synthesizes a metric whose pruning is provably admissible, wrap-aware for circular coordinates and double-cover-aware for unit quaternions. Experiments confirm exactness (recall $1.0$ vs an exhaustive scan under the same product metric), where the Euclidean-on-raw shortcut collapses to recall $\approx 0.5^{m}$ for $m$ rotation blocks, with up to three orders of magnitude speedup over brute force. We further contribute an incremental, self-balancing single-tree index for points under heavy churn (e.g. sliding-window LiDAR maps) or $SE(3)$ trajectories: bounded memory and faster updates than prior work, with an optional asynchronous tail-latency-bounding mode. The implementation is open source: https://github.com/jlblancoc/nanoflann

Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother clustering criteria in the past three decades. In this paper we give an efficient approximation scheme for this problem that runs in sublinear time for mildly increasing $k$, and thus is fixed parameter tractable with respect to the parameter $k$. We complement this result by showing that similar algorithms are unlikely to exist for the closely related problems $k$-median and balanced $k$-median, assuming popular fine-grained complexity conjectures. Specifically, we show that no sublinear time algorithm with small approximation factors can exist even for $2$-median and balanced $2$-median. It was previously known that no efficient PTAS can exist for $k$-median and our results show a strong and perhaps surprising separation between the $k$-minsum clustering problem and $k$-median even in the sublinear regime. Our upper bounds improve qualitatively upon decades old results. Our lower bounds establish the first use of the Distributed PCP framework to clustering problems.

Random Fourier features approximate a shift-invariant kernel in $\mathbb{R}^d$, such as the Gaussian kernel $\exp(-\tfrac12\|x-y\|_2^2)$, using independent samples from its spectral measure to construct an unbiased estimator for the kernel value with subgaussian concentration. However, generating $m$ such features requires $O(md)$ time. A long line of work on structured random features has accelerated this computation for the Gaussian kernel and other radial kernels, albeit with weaker concentration guarantees. We close this gap by showing a random feature map that can be computed in near-linear time $O((d+m)\log d)$ and yields near-subgaussian concentration. We obtain it through a new and tighter analysis of the Fastfood feature map of Le, Sarlós and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.

Consider an unknown graph $G = (V,E)$ with vertex degrees $d_v$, accessed only by sampling uniformly random edges and querying the degrees of their endpoints. We study the query complexity of estimating the number of edges $m$ and the degree moments $M_s = \sum_{v \in V} (d_v)^s$ for fixed integers $s \ge 2$. In this model, [Beretta and Tětek, TALG 2024] estimate $m$ within relative error $\varepsilon$ using $O(\log n/\varepsilon^2+\sqrt n/\varepsilon)$ expected queries without knowing the number of vertices $n$, and [Bhattacharya and Pradhan, CIAC 2025] estimate $M_s$ using $O(n^{1-1/s}/\varepsilon^2)$ queries when $n$ is given. We show that the query complexity of both problems is governed by the matching number $\nu$ of $G$ (the maximum number of pairwise disjoint edges) rather than the number of vertices $n$, and that the dependence on $\varepsilon$ for degree moments can be polynomially improved. Our algorithms rest on a simple observation: the endpoints of a maximum matching cover every edge, so a random endpoint of a random edge falls on this set of $2\nu$ vertices with probability at least $1/2$. For every $\varepsilon\in(0,1]$, we give advice-free algorithms that estimate $m$ and $M_s$ within relative error $\varepsilon$ with probability at least $2/3$, without knowledge of $n$, $\nu$, or other graph parameters. Specifically, our algorithms use $O(\min\{\nu/\varepsilon, 1/\varepsilon^2+\sqrt\nu/\varepsilon\})$ expected queries for $m$ and $O(\min\{\nu^{1-1/s}/\varepsilon^{2/s}, \nu^{1-1/(2s-1)}/\varepsilon^{2/(2s-1)}\})$ for $M_s$. Finally, our lower bounds show that for every $k \ge 2$ and sufficiently small $\varepsilon$, these query complexities are optimal up to constant factors over graphs with matching number at most $k$.

Given $n$ nonnegative integer weights $w_1, \ldots, w_n$ and an integer knapsack capacity $T$, the $\#$Knapsack problem asks to count the number of subsets $I \subseteq \{1, 2, \dots, n\}$ such that $\sum_{i \in I} w_i \le T$. A long line of research has been devoted to designing faster $(1 \pm \varepsilon)$-approximation algorithms for this \#P-hard problem. Until very recently, the best-known time complexity was $\tilde{O}\bigl(n^{2.5}/\mathrm{poly}(\varepsilon)\bigr)$, achieved by the randomized algorithm of [Dyer, STOC 2003] and the deterministic algorithm of [Gawrychowski, Markin, and Weimann, ICALP 2018]. The recent work by [Feng and Jin, SODA 2025] improved the randomized complexity to $\tilde{O}\bigl(n^{1.5}/\mathrm{poly}(\varepsilon)\bigr)$, leaving open the question whether this $n^{2.5}$ barrier could also be broken by a deterministic algorithm. In this work, we answer this question in the affirmative by presenting a deterministic $(1 + \varepsilon)$-approximation algorithm for \#Knapsack in $\tilde{O}\bigl(n^{2.4}/\mathrm{poly}(\varepsilon)\bigr)$ time. Our key technical innovation is to deterministically simulate the balancing technique, which was previously used in the literature of knapsack-type problems via random partitions and seemed to require randomization.

A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every value the predictor outputs, the average outcome among the members of that subpopulation who receive that value is close to the value itself. For finite classes, about $\varepsilon^{-3}$ samples are necessary and sufficient to learn a predictor with multicalibration error $\varepsilon$, but the algorithms that attain this rate enumerate the class, which is impossible for the large classes of interest. We ask how many samples suffice when the learner accesses the class only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}(d/\varepsilon^{3})$ samples and polynomially many ERM calls, where $d$ is the VC dimension of the class. Its dependence on $\varepsilon$ is optimal for all learners. When $d$ is at least about $1/\varepsilon$, every learner that can only access the class through polynomially many ERM calls needs $\tilde{\Omega}(d/\varepsilon^{3})$ samples. Learners with unlimited computation need only $\tilde{O}(\varepsilon^{-3}+d\varepsilon^{-2})$ samples, so the extra factor $1/\varepsilon$ on the dimension term is the price of oracle efficiency. For swap multicalibration, which allows a different function from the class for each predicted value, $\tilde{\Theta}(d/\varepsilon^{3})$ samples are necessary and sufficient. For estimating the error of a given predictor, the ordinary notion is the harder one: the swap error can be estimated with an ERM oracle, whereas the ordinary error is NP-hard to approximate even for classes with linear-time ERM. Consequently, there are classes for which it is computationally easier to learn a multicalibrated predictor than to compute the multicalibration error of a given predictor.

The Mallows model is a well-established construct in preference modeling, describing random rankings through their Kendall-Tau distance from a reference permutation. Its compact parameterization and interpretable treatment of preference uncertainty have made it influential across statistics, machine learning, probability, and revenue management. In the latter domain, recent literature has studied the embedding of Mallows-driven choice into assortment optimization. Early approximation schemes in this context require stylized structural simplifications or restrictive parametric assumptions. In the absence of these levers, a highly involved quasi-polynomial-time approximation scheme has subsequently been proposed, leaving wide open the question of whether near-optimal assortments can be computed in true polynomial time. The main contribution of this focused technical paper resides in closing these gaps by uncovering a striking independent-utility structure within Mallows choices, and turning this representation into a polynomial-time approximation scheme. Our central structural characterization explicitly constructs a single collection of mutually independent utilities, reproducing Mallows choice probabilities simultaneously for all offered sets. This exact choice equivalence connects pending Mallows-related challenges to the recent approximation framework of Bowers et al. (FOCS 2025) for assortment optimization under independent random utilities. We make this connection algorithmically feasible through a finite-support reduction that produces distributions of polynomial size while controlling revenue loss uniformly over all assortments. Fused together, these ingredients lead to an $O(n^{\tilde{O}(1/\epsilon^2)})$-time approximation scheme for assortment optimization under the Mallows model, while allowing arbitrary product prices, concentration parameters, and modal rankings.

Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log n)^{1-\kappa}) is governed by bounding the second moment E[X^2] < 1 of recursive branching processes over trilinear tensor carrier graphs. In this work, we present a constructive combinatorial optimization over the alternating carrier bipartite matching graphs of the Schönhage trilinear tensor decomposition at dimensions h=23 and h=25. Through an alternating augmenting path search, we uncover a non-trivial cluster-unlocking cascade that eliminates 185 carrier roles (95 roles in h=23 and 90 roles in h=25), reducing the global physical wire width by 377,890 wires from the reviewed baseline W = 177,284,805 down to W = 176,906,915. Evaluated over the exact 10^{-14} rational grid, this wire reduction certifies an improved second-moment coefficient AB = 5,164,059 / 125,000,000,000 and establishes the sharpened conditional exponent \kappa = 826,215,307 / 20,000,000,000,000 \approx 4.131076535 \times 10^{-5}, strictly surpassing the preceding record on this architecture (\kappa \approx 4.123864 \times 10^{-5}). All 47 polynomial constraints and 7 rational security margins are audited in exact Q-arithmetic with zero floating-point error, and the fundamental wire reduction identity is formally verified in the Lean 4 interactive theorem prover without unproven axioms.

LeetCode Problem 856, Score of Parentheses, admits a one-pass algorithm using $O(n)$ time and $O(1)$ auxiliary registers. Its correctness follows from a local interpretation: every occurrence of () contributes a power of two determined by its nesting depth. The space bound is immediately optimal in the usual programming-challenge model, but the linear-time bound is less obvious. In particular, a direct adversary that forces an algorithm to inspect every character is difficult to maintain under the promise that the input is balanced. We instead prove a counting lower bound. For every $k$, we construct $2^k$ balanced parenthesis strings of the same length $4k+2$, all having distinct scores. The construction encodes each bit using one of two operations, changing a current score $v$ to either $2v+1$ or $2v+2$. Consequently, any deterministic character-query decision tree computing the score must have depth at least $k$. A two-character padding argument extends the result to every even input length, proving an $\Omega(n)$ worst-case time lower bound. The one-pass algorithm is therefore asymptotically optimal in the unit-cost RAM model.

Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player. The respective player chooses outgoing edges from their vertices. We consider these games with the classical discounted-sum and mean-payoff objectives. The goal of the Max Player is to maximize the objective against the adversarial Min Player. These games lie in NP $\cap$ coNP and are among the rare combinatorial problems that belong to this complexity class, yet the existence of a polynomial-time algorithm is a major open question. All known deterministic algorithms require exponential time in the worst case, while the classical strategy iteration (policy iteration) algorithm is remarkably efficient in practice, which motivates the study of the smoothed complexity of these games. Previous results established a smoothed polynomial-time bound only for the restricted class of ergodic games and presented only a high-probability guarantee. Our main result is a new analysis technique for a variant of the strategy iteration algorithm, and we show these algorithms achieve smoothed polynomial complexity for general game graphs with both high-probability and expected runtime guarantees. In particular, our result removes the ergodicity restriction of prior work and strengthens the high-probability guarantee to the stronger expected-runtime guarantee, thereby resolving the open question on the smoothed complexity of these games.

The arboricity of a graph is the minimum number of forests needed to partition its edges. We present a randomized algorithm that computes the exact arboricity of a simple graph and constructs an optimal forest partition in $\min\{n^{2+o(1)},m^{4/3+o(1)}\}$ time both in expectation and with high probability, where $n$ and $m$ denote the numbers of vertices and edges. In particular, it runs in almost-linear time, $O(m^{1+o(1)})$, on dense graphs with $m=\Theta(n^2)$. We also give the first known almost-linear-time algorithm that constructs a partition into at most one more forest than optimal.

Federated clustering can support applications such as patient stratification across hospitals and customer segmentation across distributed financial datasets. Responsible AI calls for fair representation of demographic groups and support for data deletion, motivated in part by rights such as the GDPR's right to erasure. These goals interact: deleting records can change the balance between groups and alter the clustering of the remaining population. We study exact machine unlearning for federated socially fair $k$-means, whose objective is to minimize the largest group-average squared distance to the nearest center. Our approach keeps separate local summaries for each group, so summaries at unaffected institutions remain valid as global fairness weights change. For two groups, we prove an initialization approximation guarantee independent of client group proportions under ideal sampling, and we show that same-seed replay reproduces retraining exactly. Reuse pays off most when a whole client withdraws: across three datasets, replay is $35.8\times$ faster than retraining for the initialization-only model and remains $2.4\times$ and $1.7\times$ faster with one and two fair-refinement rounds, which improve worst-group cost. For individual record deletions, gains are modest (about $1.06\times$), and certifying cached assignments can cost more than it saves. These results map where exact unlearning can profitably reuse computation. Code and reproducibility materials are available at https://github.com/arareddy/mufsc.

We study the $k$-Canadian Traveller Problem (k-ctp), an online navigation problem introduced by Papadimitriou and Yannakakis in 1991. Given an undirected weighted graph $G=(V,E,\omega)$ and two vertices $s,t\in V$, a traveller aims at navigating from $s$ to $t$ while minimizing the total distance travelled. However, up to $k$ edges of the graph may be blocked, and the traveller discovers that an edge is blocked only upon reaching one of its endpoints. The performance of an online algorithm for k-ctp is measured with the competitive ratio, which is the quotient between the distance actually traversed and the distance traversed by an omniscient traveller who knows all blockages in advance. A general lower bound $2k+1$ for the competitive ratio of deterministic algorithms remains valid even when the input graph is series-parallel, whereas constant competitive ratios can be achieved on restricted graph classes, such as cycles or unit-weighted outerplanar graphs. In this paper, we establish the first intermediate competitive ratio between constant and linear regimes. We prove that, on unit-weighted solid grid graphs, there exists an online algorithm with competitive ratio $O(\sqrt{k})$. This ratio is asymptotically tight and cannot be defeated, even on unit-weighted square grids. Finally, we show that both the unit-weighted and solidity assumptions are essential: going further with arbitrary edge weights (even on square grids) or non-solid unit-weighted grid structures yields a linear lower bound of $\Omega(k)$.

We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than $2$. Given $k$ randomized online experts and $0<\varepsilon<1$, we construct a randomized online algorithm whose realized total cost is always at most $(2+\varepsilon)$ times the offline optimal cost $\mathrm{OPT}$ and whose expected regret against the expert with the smallest realized cost is $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$. The algorithm requires no advance knowledge of the number of packets or $\mathrm{OPT}$. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for $k\ge 2$, this regret bound is asymptotically optimal in $\mathrm{OPT}$, $k$, and $\varepsilon$, and that $\varepsilon>0$ is necessary for sublinear regret.

We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{{O}}(n^{2/3})$ per query/update [Subramanian, ESA '93]. This can be improved to $\widetilde{{O}}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA '07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS '16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low “stabbing number” [Chazelle and Welzl, Discrete Comput. Geom. '89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.

We give deterministic algorithms for approximating the girth~$g$ of an undirected graph with $n$ vertices, $m$ edges, and nonnegative real edge lengths. For every integer $k\geq2$, our algorithm returns a cycle of length at most $\frac{2k}{3}g$ in $O((m+n^{1+2/k})k\log n)$ worst-case time. For every constant~$k$, this matches the stretch and the expected running time of the randomized algorithms of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'23, SICOMP'26] and Kadria, Roditty, and Vassilevska Williams [ESA'26]. In general, it loses only a factor of $O(\min\{k,\log n\})$ in the term that depends on~$m$. The best previous deterministic trade-off, of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'22], has stretch~$k$ instead of $\frac{2k}{3}$ at the same exponent (for even~$k$) and requires integer edge lengths. In particular, for $k=3$ we obtain a deterministic $2$-approximation in $O((m+n^{5/3})\log n)$ time for real edge lengths, whereas the deterministic algorithm of Ducoffe [SIDMA'21] for real lengths has stretch $2+\varepsilon$. Our main technical idea is that a deterministic construction of the Thorup–Zwick hierarchy used by these algorithms may stop exploring as soon as it finds a cycle: the approximation analysis only needs clusters truncated at half the best cycle certificate found, so balls stopped in this way need not be hit. Together with a degree-weighted selection rule, this bounds the work of each level by its number of edges and stored ball entries. More generally, a ball need not be hit whenever the analysis only uses clusters up to a radius bounded by a certificate that the algorithm has already found.

Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has directed treewidth at least $f_c(k)$, then it contains a bramble of size at least $k$ and congestion at most $c$. By the Directed Grid Theorem of Kawarabayashi and Kreutzer [STOC 2015], such a function $f_c(k)$ exists for every value $c \geq 2$ of the congestion. However, even using the recent improvements due to Hatzel et al. [FOCS 2024], the resulting function is a power tower of height $22$. Recently, Masařík et al. [SIAM J. Discrete Math. 2022] proved that, for congestion $8$, the function $f_8(k)$ can be made polynomial; more precisely, they showed that $f_8(k) = \mathcal{O}(k^{48} \cdot \log^{13} k)$. They asked whether it is possible to decrease the congestion, ideally to $2$, even at the cost of a higher polynomial function. In this work we answer their question affirmatively with the best possible value of the congestion, by proving that $f_2(k) = \mathcal{O}(k^{96}\cdot \log^{23} k)$. We also obtain smaller polynomials for higher congestion, namely $f_4(k) = \mathcal{O}(k^{72} \cdot \log^{21} k)$ and $f_6(k) = \mathcal{O}(k^{66} \cdot \log^{18} k)$. Our results are inspired by the proof for congestion $8$, which we improve by introducing walkages. Walkages allow us to avoid technicalities of the original proof by translating ideas due to Reed and Wood [Eur. J. Comb. 2012] that work for undirected graphs to the directed setting. Our proofs are constructive and naturally yield polynomial-time algorithms to find the brambles assuming a certificate for large directed treewidth is given. Moreover, we discuss algorithmic applications of our results for the Directed Disjoint Paths with Congestion problem, and to half-integral packings of subgraphs with large directed treewidth.

Model minimization is a fundamental problem in formal methods, as smaller models can substantially reduce the complexity of model analysis and reasoning while preserving relevant semantic properties. This work studies the minimization of finite fuzzy Kripke models over residuated lattices while preserving global or local assertions in fuzzy modal logics, which are either fuzzy propositional dynamic logic or a restriction thereof, optionally enriched with nominals, converse modalities, and/or the universal program constructor. We prove that, whenever the multiplication operator of the underlying residuated lattice is right-continuous, the quotient model induced by the greatest fuzzy auto-bisimulation is a minimal reduction preserving global assertions. If the underlying fuzzy modal logic includes the universal program constructor, this quotient model is also a minimal reduction preserving local assertions and a minimal fuzzy Kripke model bisimilar to the original model. In the case where the universal program constructor is absent and the multiplication operator is additionally strictly monotone with respect to~1, we present the first algorithm for constructing a minimal reduction preserving local assertions; the resulting model is also a minimal bisimilar model.

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a “value” to each type, and prioritizes matches with high “surplus” (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

We give an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for multidimensional subset sum on an explicitly listed multiset of $n$ vectors in $[-N,N]^d$, for every fixed $d$ and $\varepsilon>0$. This directly implies an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for feasibility test of integer programming. Prior to our work, the best-known algorithm has a running time of $O_{d}(n+N^{O(d^2)})$ [Eisenbrand, Weismantel'19]. Specifically, if $d=1$, our algorithm runs in $O_{\varepsilon}(n+N^{1+\varepsilon})$-time for the standard subset sum problem, which is near-linear in the largest input integer. Prior to our work, subset sum can be solved in time near-linear in the target $t$ [Bringmann'17], or near-linear in the mixed parameter $\sqrt{Nt}$ [Chen, Lian, Mao, Zhang'24]. It is a fundamental open problem whether the algorithm can be made near-linear in $N$, which is settled affirmatively in this paper up to an arbitrary small $N^{\varepsilon}$ term.

We study static indexes for exact subsequence matching over all equal-length windows of a time series. Under deterministic SETH, for every fixed $\beta\ge1$ and $\delta\in(0,1)$, we exclude $O(N^\beta)$ preprocessing together with $O(N^{1-\delta})$ worst-case query time on domains containing the reduction's polylogarithmic query lengths. The bounded-error counterpart assumes randomized SETH. The results cover specified warping, bottleneck, edit, subsequence, local-alignment, and complexity-adjusted scores. Their reductions share a data-independent query interface but require different arguments for all-window soundness. We give complete representative proofs for the distinct mechanisms and state the changes needed by related scores. For soft-DTW, integer scaling yields an exact Boolean-predicate reduction in Word-RAM; a model with exact transcendental primitives requires a separate assumption. For independent window-wise Z-normalization, balanced coordinate gadgets and shifted-window moment bounds yield exact lower bounds for squared-cost DTW and discrete Fréchet distance. We give finite-word comparisons and a specified length-dependent rounding rule preserving these gaps. Raw and normalized discrete Fréchet constructions also exclude feasible-solution approximation within any fixed factor below two. Finally, we prove conditional signal-attenuation bounds for normalized anchor constructions and a fast index under the all-window common-mean promise.

We give a polynomial-time randomized classical algorithm that approximates the largest eigenvalue $\lambda_{\max}$ of a traceless quartic fermionic Hamiltonian $H$ on $n$ modes. The algorithm achieves energy at least $\lambda_{\max}/O(\sqrt n)$ and outputs either a fermionic Gaussian state or a polynomially sparse state in the Fock basis. This is achieved through a new upper bound on $\lambda_{\max}$ in terms of the maximum energy of a Gaussian state and $\sqrt{2^{-n}\operatorname{Tr}(H^2)}$.

We construct exact deterministic circuits for transposing and inverting an unknown qutrit unitary $U\in\mathrm{SU}(3)$ using only forward queries. Three queries prepare a catalyst independently of the input state. Four further queries implement transposition while returning the catalyst unchanged and uncorrelated with the output. Two uses within an antisymmetric encoding implement inversion with eight processing queries and return the same catalyst. Reusing the catalyst implements $m$ transpositions or inversions with $3+4m$ or $3+8m$ total queries, respectively. More generally, we prove that exact transposition and inversion of an unknown $U\in\mathrm{SU}(d)$, $d\ge2$, require at least $d+1$ and $d^2-1$ processing queries, respectively, in fixed causal order. These processing bounds hold for any program state prepared independently of the input state using finitely many forward queries, even if that state is consumed during processing. Both our catalytic qutrit algorithms attain their respective bounds. Moreover, exact qutrit transposition with four processing queries requires at least three preparation queries, and our construction attains this bound.

For $\Delta\ge2$ and $q\ge11\Delta/6$, we prove that the antiferromagnetic $q$-state Potts partition function on finite simple graphs of maximum degree at most $\Delta$ has no Fisher zeros in a graph-uniform complex neighbourhood of $[0,1]$. For $q>11\Delta/6$, the proof establishes coupling independence throughout $[0,1]$ using a soft version of Vigoda's flip dynamics. Our main tool is a separator-shell transfer theorem for the Potts model on induced-subgraph closed classes of graphs of maximum degree at most $\Delta$, with $q\ge\Delta+1$. It yields a graph-uniform zero-free neighbourhood of $[0,1]$ from Hamming coupling independence at $0$ and a uniform coupling-independence bound on each interval $[\delta,1]$, $\delta\in(0,1]$. We also obtain zero-free Lee-Yang polydiscs around the uniform field for vertex- and edge-colour fields. For Boolean Holant problems on bounded-degree graphs whose signatures come from a fixed finite family of log-concave symmetric signatures $f$ with $f(0)>0$, such as $b$-matchings, we obtain graph-uniform zero-free polytubes around every bounded box of nonnegative activities; their union is an open zero-free neighbourhood of the nonnegative orthant. An appendix summarizes further coupling-independence inputs and the zero-free regions they yield.