Papers

In apparel retail and other applications, when a customer's preferred size is unavailable, demand may shift to nearby sizes. This substitution creates new assortment and inventory optimization challenges by coupling product availability and demand across sizes. We introduce the consider-fit-then-choose (CFTC) model to capture such size-dependent choice behavior. Products may be offered in multiple sizes, which affect customer preferences and consideration sets through fit, measured by distance from the customer's ideal size. We study assortment optimization and show-all inventory selection, in which the retailer chooses initial inventory and subsequently offers every in-stock product. We show that assortment optimization under the CFTC model is NP-hard and develop a PTAS when customers deviate by at most $O(1)$ sizes from their ideal size. Combined with the recent black-box framework of Fu et al. (2026), this yields a nearly $0.272$-approximation for show-all inventory selection. We next exploit the specific choice dynamics of the CFTC model. By stocking only every other size, we decouple demand across stocked sizes and reduce CFTC to a special class of mixed multinomial logit models that we prove satisfies the convex chain decomposition (CCD) property of Goyal et al. (2023). For the fluid problem, we develop a polynomial-time $(1/2-\epsilon)$-approximation under adjacent-size substitution and a mild condition on preference weights. For the stochastic problem, we establish an asymptotic $1/2$-approximation using a new coupling argument connecting the stochastic inventory process to its fluid counterpart. Numerical experiments calibrated using footwear data show small optimality gaps across a broad range of substitution patterns and problem settings.

We study interval scheduling from the perspective of fair allocation. There are $m$ identical machines and a set of intervals, each specified by a start time, an end time, and a nonnegative weight. A schedule assigns a subset of the intervals to the machines so that no two intervals on the same machine overlap, and the goal is to maximize the total weight of scheduled intervals. Viewing machines as agents and intervals as goods, we require the schedule to be envy-free up to one item (EF1), and we measure efficiency against the offline optimum without fairness. In the offline setting, we give an algorithm that computes an EF1 schedule whose loss is at most a factor of $3/2$ in the unweighted regime, and we prove lower bounds of $\frac{3m-2}{2m-1}$, approaching $3/2$, in both the unweighted and the unit-length weighted regimes, so the price of fairness is $3/2$ in the limit. In the online setting, intervals arrive in nondecreasing order of start times; an arriving interval must be accepted or rejected, rejections are irrevocable, and an accepted interval may be revoked, and lost, at any time before it ends. For the unweighted regime we present Greedy-Balanced, a simple algorithm that maintains EF1 at every point in time and is $(2-\tfrac{1}{m})$-competitive against the offline optimum without fairness, and we prove a matching lower bound for every deterministic algorithm; the optimal deterministic fair competitive ratio is thus exactly $2-\tfrac{1}{m}$. Experiments on real-world benchmark instances show that Greedy-Balanced performs well beyond its worst-case guarantee, with an observed ratio never exceeding $1.306$.

For a convex function $f \colon \mathbb{R}^d \to \mathbb{R}$, the problem of sampling from a distribution proportional to $e^{-f(x)}$ is called log-concave sampling. In many practical scenarios, the function $f(x)$ turns out to admit a local decomposition $f(x) = \sum_{a=1}^R \psi_a(x_{S_a})$. In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause $\psi_a(\cdot)$, which can be computationally much cheaper than the queries to $f(x)$ itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using $\widetilde{O}(\sqrt{\kappa}d)$ local queries, where $\kappa$ is the condition number. This improves the prior best classical result $\widetilde{O}(\kappa d)$ due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result $\widetilde{O}(\sqrt{\kappa} d^2)$ implied by Childs et al. (NeurIPS 2022). Our quantum sampler applies to a broad class of locally structured models from statistical computing and machine learning, with representative examples including Gaussian Markov random fields, finite-element latent Gaussian models, and sparse generalized linear models. These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling.

Jaillet et al. introduced a fully online model for batching nonpreemptive LLM requests under a growing KV-cache memory constraint. For total end-to-end latency they proved that every deterministic algorithm has competitive ratio Omega(sqrt(n)), while the elementary sequential upper bound is n. We close this gap. Let R_det(n,M) be the optimal deterministic ratio for exactly n requests at memory M, and let R_det(n)=sup_M R_det(n,M). For every n >= 2 we prove (n-1)/12 <= R_det(n) <= n, so R_det(n)=Theta(n). The lower bound releases one memory-filling long request, observes its deterministic start time, and then releases n-1 wide one-token requests halfway through the long run. No short request can overlap the long one, whereas a hindsight schedule runs the two groups in the opposite order when useful. The hard instance uses the explicit fixed memory M=2(n-1)n. The upper bound is achieved by a uniform causal serial policy. The exact model, causality argument, both comparator branches, and quantifier order are machine-checked in Lean 4. Exact finite controls and replay commands accompany the proof.

The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investigated for more than five decades, compared to graphs, there are only very few results on the isomorphism problem of tournaments. For most classes of tournaments neither hardness nor polynomial-time solvability is known. Tournaments of bounded VC dimension are such a class for which no results are available, even though the VC dimension is arguably one of the most robust and central notions of combinatorial tameness. Resolving an open problem of Neuen and Grohe, we show that the isomorphism problem for tournaments of VC dimension $d$ can be decided in time $n^{O(d\log d)}$. Consequently, automorphism groups of tournaments of bounded VC dimension can be computed in polynomial time. To this end, we develop a new method to isomorphism-invariantly decompose tournaments. To facilitate recursion, we introduce the notion of a patched tournament and analyze bounded VC dimension in patched tournaments. We design a recursive algorithm that balances the size of the decomposed pieces against their number and makes use of the structure of near twins. In an orthogonal direction, it is known that a hereditary class of tournaments has unbounded VC dimension if and only if it contains all 2-colorable tournaments. As a second result, we show that also this class does not form an obstruction towards polynomial-time isomorphism testing and indeed show that isomorphism of tournaments of bounded chromatic number is polynomial-time decidable.

For $d \geq 2$, $p \geq 1$ and $\epsilon > 0$, let $N_p(d,\epsilon)$ be the smallest integer $N$ such that for every integer $n$ and every $A\in\mathbb{R}^{n\times d}$, there exists a matrix $\Phi\in\mathbb{R}^{N\times n}$ satisfying $(1-\epsilon)\lVert Ax\rVert_p\leq \lVert\Phi A x\rVert_p\leq (1+\epsilon)\lVert Ax\rVert_p$ for all $x\in\mathbb{R}^d$. For every constant $p\geq 1$ with $p\not\in 2\mathbb{Z}$, when $d\gtrsim_p \log(1/\epsilon)$, the bound \[ N_p(d,\epsilon) \gtrsim_{p} \frac{d}{\epsilon^2 \operatorname{polylog}(d/\epsilon)} \] is established. This improves the previous lower bound $\Omega(1/(\epsilon^2\operatorname{polylog}(1/\epsilon)))$ due to Li et al. (SICOMP 2021) and is optimal up to logarithmic factors for $1\leq p<2$. The central technical idea originated from ChatGPT 5.6 Sol.

We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of equal aligned character pairs, as in the classical longest common subsequence problem, and then, among all such alignments, to minimize the alignment length. Equivalently, after maximizing the number of equal pairs, we minimize the number of insertions and deletions. We show that this problem admits a simple block-boundary dynamic program. If the input strings have lengths $N$ and $M$, and their run-length encodings have $n$ and $m$ runs, respectively, the algorithm runs in $O(mN+nM)$ time using $O(nm)$ space. The algorithm treats every pair of runs as a homogeneous block with an explicit transfer function and stores dynamic-programming values only on run boundaries.

We prove weighted matroid equitability. Let $M=(E,\mathcal{I})$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every element. Then $E$ has a partition into $k$ bases such that the weights of any two bases differ by at most the largest element weight. We present two proofs based on the localized exchange theorem of Akrami, Liu, Raj, and Végh. The first is existential, while the second is constructive and leads to a strongly polynomial-time algorithm. As applications, we obtain an additive guarantee for matroid-constrained makespan minimization for identical machines and a strongly polynomial-time algorithm for finding an EF1 allocation under a matroid constraint and identical additive valuations. We further generalize the Beck–Fiala framework in discrepancy theory to settings with matroid constraints. Given a nonnegative matrix of column sparsity $\Delta$, we show that a fractional basis can be rounded to a basis of no larger cost while preserving every row sum within additive error $2\Delta$ times the largest matrix entry. Motivated by the $2$-sparse prefix Beck–Fiala conjecture, we formulate a conjecture on prefix-constrained matroid bases and prove a discrepancy bound $O(\log n)$. Finally, we give a counterexample to the weighted carpooling conjecture, thereby also disproving a conjecture by Morell and Skutella on single-source unsplittable flows with two-sided discrepancy bounds.

In this paper, we address a semi-infinite LP relaxation of the vector-subspace packing problem. This is a higher-dimensional generalization of the fractional linear matroid parity problem and is closely related to Brascamp-Lieb polytopes. We show that the dual of this LP can be formulated as “linear programming on a Euclidean building," namely, the problem of minimizing a Busemann function over an intersection of horoballs. This provides a natural example of horospherically convex optimization, recently introduced by Goodwin et al. (2026) and Criscitiello and Kim (2025). By applying the incremental Busemann subgradient method, we obtain an additive FPTAS for the problem. As applications, we obtain a new and simpler polynomial-time algorithm for fractional linear matroid parity, and new algorithms for the membership problem of Brascamp-Lieb polytopes.

Near capacity, a cuckoo filter may reject an insertion even though a legal placement still exists: the table remains structurally feasible, but a bounded policy fails to find an augmenting path. Random kick-out keeps each step cheap but leaves no persistent direction; breadth-first search recovers direction by expanding a frontier and maintaining table-scaled state. CavityRank exploits a resource already present in four-slot packed buckets. Lookup observes only the fingerprint multiset, so query-equivalent lane orders can encode two comparison bits without widening the 64-bit bucket or changing the two-bucket query. The bits form a four-level ordinal residual rank. Insertion follows a minimum-rank edge and re-encodes each modified bucket from its outgoing edges after relocation, propagating the rank actually realized by the packed word. An exact capacity-four orientation oracle separates structural infeasibility from bounded-search loss. In a paired 4,096-bucket XOR16 ladder, CR2 closes 86.47% of Random CF's oracle gap and CavityRank leaves 1.39% of that original gap. A canonical-tie CR2-versus-CavityRank ablation isolates the second implicit bit, which closes 89.95% and 90.69% of CR2's residual gap; the corresponding closures at 65,536 buckets are 83.95% and 84.27%. A separate packed implementation study at 64 MiB and 97.75% load records 42.53 logical reads per insertion, versus 62.67 for explicit labels and 355.74 for depth-10 BFS, with zero extra bytes per bucket and no table-scaled workspace. CavityRank therefore occupies a practical design point between unguided eviction and frontier search.

A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted $n$-vertex, $m$-edge multigraph, let $0<\varepsilon\le1/2$. Assuming $m,\varepsilon^{-1}\le n^{O(1)}$ and the ratio of maximum to minimum weight is polynomially bounded, we deterministically construct a $(1\pm\varepsilon)$-spectral sparsifier with \[ O\!\left(n\varepsilon^{-2}\log^{24+o(1)}n\right) \] edges in \[ m^{1+o(1)}+O\!\left(n^2\varepsilon^{-9/2}\log^{113/2+o(1)}n\right) \] time. The construction has two main ingredients. First, we sparsify an approximately regular expander by partitioning its edges into few matchings and viewing their normalized Laplacians as an isotropic family of positive semidefinite matrices. Rather than sample from this family and apply matrix Chernoff, we select matchings deterministically using a pessimistic estimator. We evaluate the resulting conditional-expectation scores in two ways to produce two algorithms: using dense matrix multiplication and sparsely using polynomial approximations to the inverse square root and matrix exponential. Deterministic expander decomposition, along with replacing vertices by fixed expander graphs to achieve approximate regularity, extends these algorithms to general graphs. Second, a recursive blocking scheme applies the dense algorithm to smaller subgraphs and the sparse algorithm to their union, balancing their costs. Reusing the resulting algorithm as the dense algorithm gives $\alpha_{r+1}=3-1/(\alpha_r-1)$, starting from $\alpha_0=\omega$. After $O(\log n)$ levels, the exponent is $2+O(1/\log n)$, yielding $m^{1+o(1)}+\widetilde O_{\varepsilon}(n^2)$ time.

We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location $y$ clears all pending requests in $[0,y]$ at cost $y$. In the classical adversarial setting, we propose an $e$-competitive randomized algorithm against an oblivious adversary and prove a matching lower bound. Thus $e$ is the optimal randomized competitive ratio. We then consider advice in the form of an offline feasible solution. For every confidence parameter $\lambda\in(0,1]$, our deterministic learning-augmented algorithm is $(1+3/\lambda)$-robust and $(1+3\lambda)$-consistent. We also propose a randomized learning-augmented algorithm that is $(e+e/\lambda)$-robust and $(e-1+\lambda)$-consistent against an oblivious adversary. For the offline problem, we present a polynomial-time dynamic programming algorithm. Numerical experiments complement the worst-case analysis: accurate advice lowers service costs, while both learning-augmented algorithms remain stable as the advice becomes increasingly noisy.

We resolve the conjecture of Koutis and Williams that $k$-paths can be approximately counted in $O^*(2^k)$ time. For a simple directed graph with $n$ vertices and $m$ arcs, our randomized algorithm returns a $(1\pm\varepsilon)$-approximation with failure probability at most $\delta$ in $O^*(2^k\varepsilon^{-2}\log(1/\delta))$ time.

We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time $\widetilde O(m+n)+\widetilde O_\beta(n^2\log^2 (1 / \varepsilon))$, where $n$ and $m$ are the numbers of vertices and edges, respectively, and $\varepsilon$ is the approximation error. Our approach combines Benczúr–Karger cut sparsification with a new mixing time analysis of the Glauber dynamics for the random-cluster model. The mixing time analysis features a new monotone edge-count Poincaré inequality.

The Johnson–Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ \Theta\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen–Nelson and Alon–Klartag, holds even for nonlinear embeddings.

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of $H$ on every sequence, but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weak-learning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of $H$ at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the "dual view" of boosting: When the algorithm's randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees on every time interval. The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on $O(d^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires $\Omega(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.

In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the recent lower bound by Chen, Tan, and Xu who showed that a toroidal grid requires at least $3$ trees for constant stretch. Our result is obtained by establishing a connection between tree covers and Assouad–Nagata dimension and then invoking the recent dimension bound for minor-free metrics by Liu.

Let $K\subset\mathbb{R}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance $\varepsilon$ from the uniform distribution on $K$ in $O\!\left(n^2\psi_n^{-2}\log^3(M/\varepsilon)\right)$ steps, where $\psi_n^{-1}$ is the Kannan-Lovász-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same $n^2\psi_n^{-2}$ dependence for hit-and-run, but with polynomial dependence on $M/\varepsilon$. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.

Compactly representing a variation graph is a core problem in computational pangenomics that is usually attacked with techniques that have been originated on texts and adapted to graphs. In this paper we propose a new framework that takes a topology-centric perspective instead. A variation graph is modeled as a directed acyclic graph (DAG) together with a set of distinguished paths, where each path is assigned a distinct color. Our compact representation is centered on pebbling the graph, i.e. placing colored pebbles on edges so that every predefined path can be univocally reconstructed from the pebbled edges. In particular, a saturated pebbling marks each chosen edge with every path (color) traversing it. We first propose a data structure to represent and query a variation graph with storage space depending on the size of the pebbling. The supported queries are: (i) path query, which recovers a path given its color, and (ii) edge query, which reports the colors of paths traversing a given edge. We then prove that the problem of finding a pebbling of minimum size is solvable in polynomial time. On the contrary, we prove that finding a saturated pebbling of minimum size is NP-hard, but can be reduced to the minimum-weight set cover problem, allowing us to leverage integer linear programming (ILP) solvers. We show how to exploit saturated pebblings to achieve faster queries times than minimum size pebbling. Our framework opens a new algorithmic viewpoint on developing more efficient variation graph representations rooted on the study of the topology of those graphs.

We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et al. [Universal reconstruction of a string, Theoretical Computer Science 2020] to two dimensions, we obtain a linear-time procedure that finds a solution for any such input system. As an immediate by-product, this yields an optimal-time algorithm for decompressing any two-dimensional macro scheme based on copy operations of sub-squares.

The Lovász Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with $o(\log n)$ randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Triangle-free coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 2013, Information and Computation 2015] uses $\frac{\Delta}{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln \Delta$) and consists of $O(k+\log^* n)$ applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require $O(\log_\Delta n)$ or $O(\frac{\Delta}{\log\Delta})+\log^{O(1)}\log n$ rounds. In this work, we adapt the Pettie-Su's algorithm so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the 'resilience' definition of Davies [SODA 2023]. This gives an $O(k)+ \log^{O(1)}\log n$ complexity (since the LLL is not needed when $k= \log^{\omega(1)}\log n$), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first $\log^{O(1)}\log n$-round algorithms for coloring triangle-free graphs with $o(\Delta)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)\Delta/\ln \Delta$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.

In restricted assignment - makespan minimization where each job has one size and a set of allowed machines - the configuration LP is the tightest studied relaxation, and its integrality gap is open in general. On two-weight graph balancing - each job allowed on at most two machines, sizes from two values - the value is known, both bounds due to Jansen, Land, and Maack (2016): their Table 1 instance attains 3/2, and their Corollary 11 bound of 2 - s/b for sizes s < b meets it at {1,2}. We ask how small such an instance - a witness - can be. We give I*, a six-job witness: the complete graph on four machines, unit jobs on a Hamiltonian cycle, weight-2 jobs on the complementary perfect matching, with integral optimum 3 against relaxation value 2. That is one job fewer than the smallest previously in print, and we prove it minimum and unique at its size. No instance of the class with at most five jobs reaches gap 3/2, on any number of machines; at six jobs, again on any number of machines, I* is the only witness, up to relabeling machines and adding machines no job can use. At seven jobs uniqueness fails: exactly thirteen witnesses, classified - the Jansen-Land-Maack instance among them - and at eight jobs exactly 154. Three machines never suffice, at any size: four are necessary for the gap. Results of this shape are in print for the same relaxation in one-dimensional cutting stock, where the extremal non-round-up instances have been enumerated and classified for small demand; the Discussion sets out the relation. Recognizing witnesses at relaxation value 2 - where all of ours live - is coNP-complete, so no min-max characterization exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating point and in exact rational arithmetic, with full agreement, and the pipeline must rediscover I* before its negatives are believed.

A $d$-shortcut of a directed graph $G=(V,E)$ is a subset of edges drawn from the transitive closure $TC(G)$ whose addition reduces the graph diameter to at most $d$. In the special case $d=1$, computing a $1$-shortcut is equivalent to computing the transitive closure. For larger values of $d$, a lower bound of [Hesse, SODA 2003] shows that $n^{\delta}$-shortcuts, for small constants $\delta>0$, may still contain a large fraction of the edges of $TC(G)$, suggesting that shortcut construction may remain as hard as transitive closure even in this regime. Consequently, since $\widetilde{O}(d)$-depth parallel reachability algorithms rely on computing $d$-shortcuts, achieving $\widetilde{O}(1)$ depth by this approach has so far required computing the full transitive closure. Assuming $\omega=2$, the PS-AE-Triangle hypothesis of [Abboud, Bringmann, Fischer, and Künnemann, SODA 2024] yields a conditional $T^{4/3-o(1)}$ time barrier for computing transitive closure when $T\leq n^{3/2}$, where $T=|TC(G)|$. In this work, we bypass the transitive-closure barrier for $\widetilde{O}(1)$-depth parallel reachability. We introduce randomized $d$-shortcut constructions that already circumvent this barrier for $d=3$ and, more generally, for every even $d\geq4$ up to $O(\log n)$. Our approach yields a randomized $\widetilde{O}(1)$-depth parallel reachability algorithm with total work $\widetilde{O}(T^{\omega/2})$, which becomes $\widetilde{O}(T)$ when $\omega=2$, falling below this conditional $T^{4/3-o(1)}$ barrier throughout that regime. Under the current bound of $\omega$, this gives $\widetilde{O}(T^{1.186})$ work, improving on the current $T^{1.3459+o(1)}$ sequential-time bound for transitive closure due to Abboud et al. Thus, although $\widetilde{O}(1)$-shortcuts might be almost as dense as the full transitive closure, they can nevertheless be computed substantially faster.

Given a simple, undirected, and unweighted graph $G$, and an integer $R$, the objective of the Minimum Eccentricity Shortest Path (MESP) is to decide whether there exists an isometric path $P$ in $G$ such that the distance from every vertex in the graph to its nearest vertex in $P$ is at most $R$. In this paper, we prove that MESP admits an $O(n^4)$-time algorithm on $K_{2,3}$-minor-free graphs. Our algorithm has a cubic running time when the inputs are restricted to a cactus.

We consider estimation of non-integer frequency moments $F_k$ and related Bernstein-type statistics in the Delphic set stream model under a bounded-frequency assumption: every universe element appears at most $\tau$ times. The main challenge of this model is to keep space low while also keeping update time low, which is not trivial because the sets can be exponential in size compared to their representations. Our core insight is that by sampling the stream at different rates and observing the resulting distinct-counts, we can 'probe' the frequency distribution and numerically integrate these probes to reconstruct a broad class of statistics. Building on that, we crucially observe that the distinct-count of a randomly sampled substream, viewed as a function of the sampling rate, is a single analytic object whose evaluations determine a broad class of statistics via a complementary Laplace-type integral. Algorithmically we exploit this by: 1. estimating those evaluations using only standard $F_0$ (distinct-count) algorithms on sampled substreams and 2. recovering target statistics by controlled numerical integration on a judiciously chosen grid. For $F_k$ with $k\in (0,1)$ we obtain the first one-pass streaming algorithms for Delphic set streams whose space and per-set update time are $\mathrm{poly}(\log|\Omega|,\log m,\varepsilon^{-1},\log(1/\delta))$ in the practically relevant regime $\tau=\mathrm{polylog}(|\Omega|,m)$; in general the bounds are polynomial in $\tau$ and $\varepsilon^{-1}$ and logarithmic in $\delta^{-1}$. We also give a complexity-theoretic barrier explaining why lower bounds for removing the bounded-frequency assumption appear difficult: ruling out polylogarithmic algorithms for unrestricted Delphic $F_k$ would imply a linear-space threshold-counting separation.

The problem of computing diverse solutions has recently emerged as an important area of study, motivated by applications in fairness, robustness, and security. Instead of returning a single feasible or optimal solution, the goal is to output a collection of meaningfully different solutions, often measured by symmetric differences. Diverse variants have been studied using sparsification, network-flow reductions, and algebraic techniques. We investigate the fixed-parameter tractability of diverse variants of an implicit set-system problem. Given parameters $k$ and $r$ and a threshold $b$, the task is to compute $r$ feasible solutions, each of size at most $k$, whose diversity under a specified objective is at least $b$. Our main contribution is an oracle-based meta-theorem. We identify a broad class of objectives, called consistently diverse, that includes several standard measures. Assuming an exact empty-extension oracle given a forbidden set ${\sf Forb}$, which returns a feasible solution of a prescribed size avoiding ${\sf Forb}$ or reports that none exists, we obtain a fixed-parameter tractable algorithm parameterized by $k+r$. The algorithm makes at most $(2kr)^{kr} \cdot r$ oracle calls, and in each call the oracle parameter satisfies $s+|{\sf Forb}| \leq k+2kr$. Our framework unifies and strengthens previous oracle-based approaches. Compared with Kumabe's framework (ESA 2025), which gives a doubly exponential bound on the number of oracle calls, our approach achieves the single exponential bound $2^{O(kr\log(kr))}$ and directly constructs the desired tuple of solutions. We recover fixed-parameter tractable algorithms for all problems covered by that framework, with improved oracle complexity, and obtain strong bounds for diverse variants of classical graph and matroid problems.

We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using bounded base objects commonly available in hardware. Assuming that each process may have at most $\tau$ outstanding LL() operations, the best known deterministic algorithm requires $\Omega(n^2\tau + m)$ base objects (CAS objects and registers) [Blelloch and Wei, DISC 2020]. Previously, no comparable randomized algorithm was known. By employing randomization and FADD objects in addition to CAS objects, we obtain a space bound of $O(n\tau+m)$ against the weak adaptive adversary. For $m=O(1)$ this matches a lower bound for algorithms using CAS objects and registers [Aghazadeh and Woelfel, PODC 2015]. In addition, our object can be employed by quiescently history-independent (QHI) algorithms: Whenever no operation on the object is pending and no process has an outstanding LL() operation, its internal memory state is uniquely determined by the values of the $m$ LL/SC objects. An important application is a recent QHI dynamic hashing algorithm, which uses $\Theta(m)$ hardware LL/SC objects to maintain a hash table of size $m$ [Attiya, Bender, Farach-Colton, Oshman, and Schiller, STOC 2025]. But LL/SC is not available in hardware, and prior to our work no wait-free or efficient lock-free software implementation of LL/SC with similar properties was known. Our work demonstrates that one can actually implement the hashing algorithm on available hardware, without an asymptotic increase in step and space complexity, under the reasonable assumption that $m=\Omega(n)$.

The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time modifications must be near-instantaneous before the data structure is eventually rebuilt. For graph problems, a sensitivity data structure is constructed with a preprocessing time P so that the following queries can be answered quickly, preferably in $O(1)$ time: given an edge $e$, return the answer to the problem on either $G \setminus e$ (decremental) or $G \cup e$ (incremental). We almost entirely settle the decremental setting for the diameter and eccentricities problems in a variety of approximation regimes by matching P to the static runtime while supporting $O(1)$-time queries, thereby improving upon all previous single-failure results [Biló, Cohen, Friedrich, Schirneck, MFCS 2021; Biló, Choudhary, Cohen, Friedrich, Krogmann, Schirneck, ICALP 2023, Algorithmica 2026]. More precisely: (1) We provide a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities; (2) For the approximate setting, we match the runtime of all known static diameter algorithms across all sparsity settings, up to an additional $1+o(1)$ factor in approximation. Conversely, for the previously unexplored incremental setting of these problems: (3) We develop new lower bounds, demonstrating that no incremental algorithm can efficiently approximate diameter, radius, or eccentricity beyond a $5/3$ factor in undirected graphs or a $2$ factor in directed graphs; (4) We introduce two new instructive techniques and demonstrate how to utilize them to construct several new algorithms. Most notably, we develop incremental single-node eccentricity approximations for both directed and undirected graphs that match our new lower bounds.

Cardinality estimation - counting the number of distinct elements in a data stream - requires a tradeoff between memory and accuracy. ExaLogLog recently established the state of the art for this tradeoff by combining wide registers with a Fisher-information-optimal maximum likelihood (ML) estimator, achieving the best known memory-variance product (MVP) among HyperLogLog variants. Here we present Arithmetic Variable LogLog (AVLL), which surpasses ExaLogLog at every memory point tested using arithmetic encoding and eliminating uncommon states to consume 64-bit words completely with 11 registers each, yielding a 5.5x register-count advantage. Its four-component blended estimator, HLDLC, exploits this density advantage to surpass ExaLogLog's ML accuracy without iterative solving. At 1 KB, AVLL achieves 1.63% width-weighted mean absolute error compared to ExaLogLog's 1.71% - a 4.7% improvement. The corresponding empirical MVP is 3.4, surpassing ExaLogLog's practical MVP of 3.78 and its theoretical optimum of 3.67. This holds at every tested size from 0.25 to 4 KB. AVLL inherits DynamicLogLog's early exit mechanism, which filters most elements before any register is touched. With thousands of simultaneous sketches per thread, AVLL is 2.7-4.5x faster than ExaLogLog due to the reduced memory bandwidth from early exits. Like DynamicLogLog, AVLL stores relative NLZ values with a shared offset, so its memory scales as O(B + log log C) rather than O(B x log log C) - decoupling maximum representable cardinality from register width. These results hold under both high-complexity (all-unique) and low-complexity (nonuniformly high duplication rate) data distributions, with zero accuracy degradation from duplication. AVLL is implemented as a single self-contained Java class with all correction formulas embedded, available in the BBTools suite at https://bbmap.org.