cs.DS — Pith

Top Pith

4

cs.DS 2026-05-21 2 theorems

Generalized Thresholding Mechanism tests DP mechanisms near-optimally

by Anamay Chaturvedi, Monika Henzinger +1 more

Near-Optimal Generalized Private Testing

It accepts the first sufficiently successful mechanism from a sequence, rejects the rest, and uses a bounded number of evaluations while保持纯ε

abstract click to expand

In differential privacy (DP), the generalized private testing problem was introduced by Liu and Talwar (STOC 2019). Given a dataset $X \in \mathcal{X}$ and a sequence of black-box $\varepsilon_t$-DP mechanisms $M_t:\mathcal{X}\to\{+1,-1\}$, the analyst must accept the first mechanism whose success probability $p_t=\Pr[M_t(X)=+1]$ exceeds a given threshold $p^*\in(0,1)$, while achieving DP. Accuracy is measured by the gap between $p^*$ and a rejection threshold $\bar{p}$, such that with probability $1-\beta$ for all $t\geq1$, if $p_t\leq\bar{p}$, then $M_t$ is rejected, and if $p_t\geq p^*$, then it is accepted. This generalizes the standard private testing problem, whose solution, the Sparse Vector Technique, is ubiquitous in DP. We introduce the Generalized Thresholding Mechanism (GTM) for generalized private testing. For $\varepsilon>0$ and any sequence of $(\varepsilon_t,\delta_t)$-DP mechanisms $M_t$, the GTM is pure $\varepsilon$-DP. For $\theta>0$, $\gamma\in(1,2]$, and $\beta\in(0,1)$, $\bar{p}_t=\max(p^*/\gamma\Lambda_t, 1 - \gamma\Lambda_t(1-p^*))-\delta_t/\varepsilon_t$ for $\Lambda_t=(5t\ln^3(t+2))^{(2+\theta)\varepsilon_t/\varepsilon}(4/\beta)^{(3+\theta+2/\theta)\varepsilon_t/\varepsilon}$. With probability $1-\beta$, the number of evaluations of $M_t$ is at most $O((\ln(t/\beta)/(\gamma-1)^2)\max(\Lambda_t/p^*,(1-p^*)^{-1}))$ for all $t\geq 1$. Our lower bounds prove near-optimality of our accuracy and sample complexity guarantees. Via the GTM, we give a black-box reduction for DP optimization from the continual observation (CO) setting to the batch setting. This gives us the first DP-CO algorithms for many maximization problems. Further, the GTM permits an adaptive choice of acceptance thresholds $(p^*_t)_{t\geq1}$, addressing a challenge mentioned in prior work on using generalized private testing for hyperparameter optimization (Papernot and Steinke (ICLR 2022)).

0

Top Pith

5

cs.DS 2026-05-19 2 theorems

1-PLS of cost p yields t-PLS of cost p/t up to log n

by Arnold Filtser, Orr Fischer

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes

Near-resolution of the tradeoff conjecture shows how larger neighborhoods reduce label sizes in proof labeling schemes for general and minor

abstract click to expand

In the $t$-Proof Labeling Scheme model ($t$-PLS model), our goal is to certify that a network of nodes satisfies a given property $P$. A prover assigns a label to each node, and each node decides to accept or reject based on its labeled $t$-hop neighborhood. If $P$ holds, there exists a labeling that makes all nodes accept. If $P$ does not hold, in all labelings at least one node rejects. The cost of a scheme is its maximum label size. The Tradeoff Conjecture [Feuilloley, Fraigniaud, Hirvonen, Paz, and Perry, DISC 18, Dist. Comput.~21] hypothesizes that the existence of a $1$-PLS for a property $P$ with cost $p$ implies the existence of a $t$-PLS for $P$ with cost $O(\lceil p/t \rceil)$. The conjecture was initially shown to hold for specific graph classes, such as trees, cycles, and grids. Later, a weaker $\widetilde{O}(\lceil \Delta p/\sqrt{t} \rceil)$ cost was shown for fixed minor-free graphs, where $\Delta$ is the maximum degree. In this work we resolve the Tradeoff Conjecture, up to a single logarithmic factor. In general graphs, we show that the existence of a $1$-PLS with cost $p$ implies the existence of an $O(t\log{n})$-PLS with cost $O(\lceil p/t \rceil)$ for the same property. For fixed minor-free graphs (which include e.g. planar graphs), we show that the existence of a $1$-PLS with cost $p$ implies the existence of a $t$-PLS with cost $O(\lceil p/t \rceil+\log{n})$ for the same property. We also refute a previously suggested stronger variant of the Tradeoff Conjecture, and show that having very large $t$-hop neighborhoods is an insufficient condition for obtaining a tradeoff better than $O(\lceil p/t \rceil)$.

1 0

Top Pith

2

cs.DS 2026-05-18 2 theorems

A data structure answers c-approximate furthest neighbor queries correctly against…

by Kiarash Banihashem, Jeff Giliberti +6 more

Adversarially Robust Approximate Furthest Neighbor

Achieves query time matching the classic oblivious bound while handling adversaries that adapt to prior answers

abstract click to expand

We work in the adaptive query model, where one is given a point set $P \subset \mathbb{R}^d$ and seeks to construct a data structure that can answer correctly and efficiently a sequence of adaptive queries. In this model, an adversary observes the answers returned by the data structure to previous queries $q_1, \ldots, q_{i-1}$ and, based on this information, chooses the next query point $q_i$. This setting captures strong forms of adaptivity that naturally arise in modern machine learning pipelines, and rules out many classical randomized techniques that assume oblivious queries. Our focus is the problem of furthest neighbor search in this adaptive setting, a fundamental problem in several learning tasks, including diversity maximization, outlier and anomaly detection, adversarial example generation, and more. We present the first adversarially robust data structure for $c$-approximate furthest neighbor queries that achieves query time $\tilde{O}( \min( d n^{1/c^2}, n^{2/c^2} + d))$. This matches the $n$ dependency in the query time of the seminal result by Indyk~[SODA'03] for $c$-approximate furthest neighbor in the oblivious setting, and improves upon the $\tilde{O}(n + d)$ query time achieved via the adaptive distance estimation framework of Cherapanamjeri and Nelson~[NeurIPS'20] for a wide range of natural parameters. To complement this result, we present an adversarial attack against oblivious approximate furthest neighbor algorithms. Specifically, we show that the data structure from the algorithm by Indyk fails to maintain its guarantees against adaptive queries.

0

quant-ph 2026-07-03

k-qubit memory forces Θ(n-k) samples for stabilizer testing

by Srinivasan Arunachalam, Louis Schatzki

Optimal Stabilizer Testing and Learning with Limited Quantum Memory

The usual constant-copy tester vanishes; learning costs Θ(n²/k) non-adaptively, so testing and learning match when memory is fractional

abstract click to expand

We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown $n$-qubit state, but may keep only $k$ qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test $n$-qubit stabilizer states using $6$ copies, which is dimension independent, unlike the learning complexity of $\Theta(n)$. We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that (1) The sample complexity of testing stabilizer states in the $k$-qubit memory framework is $\Theta(n-k)$. Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group. (2) The sample complexity of learning stabilizer states with $k$ qubits of memory, in the non-adaptive framework, is $\Theta(n^2/k)$. As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with $k=0.99n$ qubits of memory, there is no constant-copy stabilizer tester; furthermore for $k=cn$ qubits of memory (for $0< c < 1$), stabilizer testing is as hard as learning, with both requiring $\Theta(n)$ copies.

0

cs.DS 2026-07-03

Heavy-edge technique yields 1.622k approx for n-pairs paths

by Avi Kadria, Liam Roditty +1 more

Improved Approximation Algorithms for n-Pairs Shortest Paths

Converts W_uv-dependent approximations to multiplicative ones in Õ(mn^{1/k} + n^{1+2/k}) time

abstract click to expand

Let $G = (V, E)$ be a graph with $n = |V|$ nodes and $m = |E|$ edges. The $t$-Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distances between $t$ prespecified pairs of vertices. Recently, this problem has received renewed attention, particularly in the case where $t = \Theta(n)$: the $n$-Pairs Shortest Paths problem. In this setting, new algorithms and conditional lower bounds have been developed by Dalirrooyfard, Jin, Vassilevska Williams, and Wein [FOCS'22], and Chechik, Hoch, and Lifshitz [SODA'25]. In this paper, we present the first algorithm for the $n$-Pairs Shortest Paths problem in \textit{weighted} undirected graphs that achieves a $(2 - \alpha)k$-approximation, for constant $\alpha > 0$, that runs in $\tilde{O}(mn^{1/k} + n^{1 + 2/k})$ time. Specifically, we present a $1.622k$-approximation, improving upon the $(2k - 3)$-approximation of Chechik, Hoch, and Lifshitz [SODA'25] for graphs that are not super sparse, which answers in the affirmative the open question posed by them. We also develop improved approximation algorithms with better tradeoffs for unweighted graphs and dense weighted graphs that improve upon the results of Dalirrooyfard \etal~and Chechik, Hoch, and Lifshitz. Our main technical contribution is the new \textit{heavy-edge} technique. Using this technique, we transform an algorithm with an approximation guarantee that depends on $W_{uv}$, the weight of the heaviest edge on the shortest path between $u$ and $v$, into an algorithm with purely multiplicative approximation that does not depend on $W_{uv}$.

0

cs.DS 2026-07-03

Sparsity bound gives poly-time deterministic exact root for sparse powers

by Qiao-Long Huang, Yichuan Cao +2 more

Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree

When total degree is bounded, the base of an exact e-th power has at most s to a power linear in D terms, so the root can be recovered deter

abstract click to expand

We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let $f \in \F[x_1,\ldots,x_n]$ be a nonzero polynomial that is an exact $e$-th power, say $f = g^e$. Suppose $f$ is $s$-sparse, has an individual degree of at most $d$, and a total degree of $D = \tdeg(f)$. We prove a sparsity bound on the base polynomial $g$: \[ \|g\|_0 \le s^{D(2d+2)/e + 1}. \] Based on this bound, we develop a deterministic algorithm that computes the base $g$. % In contrast to the general deterministic factorization algorithm of Bhargava, Saraf, and Volkovich \cite{BhargavaSarafVolkovich2020}, which achieves only a quasi-polynomial dependence on the input parameters, our algorithm is \emph{polynomial-time} in the setting where the total degree $D$ is bounded. Specifically, the overall complexity is \[ \mathrm{poly}\left(s^{O(Dd)}, n, d, D\right) + s\cdot R(e), \] % where $R(e)$ denotes the cost of constructing a single $e$-th root of a scalar in the base field $\F$, and, when $\operatorname{char}(\F)\mid e$, the cost of computing a single Frobenius root of a scalar. % This term is field-dependent, and over finite fields, $\mathbb{Q}$, or number fields with a suitable representation, it is absorbed into the polynomial complexity bound. % Within the bounded total-degree regime, this yields a deterministic polynomial-time algorithm for exact-root computation.

0

cs.CC 2026-07-03

Partition ranks lower-bound multiplicative complexity beyond bilinear

by Cornelius Brand, Petteri Kaski +1 more

Partition Rank and Algebraic Circuit Lower Bounds

Generalized ranks control arithmetic circuit complexity in constant multilinearity and recover Strassen's bilinear result.

abstract click to expand

Strassen's theory of bilinear complexity provides a mathematical characterization of the arithmetic complexity of primitives such as matrix multiplication via the rank of tensors. However, the connection to tensor rank is known to break down in higher degrees of multilinearity. In this work, we highlight an unexplored connection between a generalized notion of tensor rank, which can be defined in Naslund's framework of partition ranks (JCTA 2020), and multiplicative complexity. These partition ranks allow us to control the multiplicative complexity, and thus arithmetic complexity, in any constant degree of multilinearity from below, while recovering Strassen's seminal characterization in the bilinear case. This enables novel potential applications of the rank-based approaches to problems in fine-grained algorithms and complexity, such as the hyperclique conjecture of Lincoln-Williams-Vassilevska Williams (SODA 2018). Moreover, we exhibit connections to established notions of rank, such as tensor slice rank (in the sense of Tao and Sawin), as well as its symmetric variant. For computing the latter symmetric variant, we point out a simple NP-hardness proof, contrasting the rather involved NP-hardness proof for ordinary, non-symmetric tensor slice rank by Bl\"aser et al. (SODA 2021).

0

cs.DS 2026-07-03

Multi-secretary regret lower bound hits (log T)^2 for gapped uniforms

by Jiawei Zhang

Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates

Mixture of two separated distributions at critical capacity forces quadratic-log gap to offline optimum.

abstract click to expand

This paper studies additive regret in the multi-secretary problem, defined as the gap between the expected offline prophet reward and the reward of the best online policy. Prior work established $O(\log T)$ regret for bounded-density distributions with connected support and $O((\log T)^2)$ upper bounds for bounded-density distributions with support gaps. It was unknown whether the extra logarithmic factor is necessary even in the one-resource model. We prove that it is necessary. For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of $(\log T)^2$. Thus the existing $O((\log T)^2)$ upper bounds for bounded-density gapped instances, including those implied by network revenue management models with continuous rewards, are tight in this simplest specialization. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges; this companion result is given in the appendix. The proofs use Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion. This framework converts lower bounds into explicit certificate constructions and identifies why support gaps permit larger regret.

0

cs.DS 2026-07-03

Interleaved search makes Wheeler DFA queries 500 times faster

by Riccardo Maso, Nicola Prezza +1 more

Faster Cache-Efficient Pattern Matching for Deterministic Wheeler Pangenome Graphs

Binary search plus sequential scans on pangenome graphs trades 15x space for sub-3ns per character processing.

abstract click to expand

Pattern matching on strings is regarded as one of the core operations in computer science. Although researchers proposed several solutions to this problem, some of the most elegant and widely used approaches are based on the renowned Burrows-Wheeler transform (BWT). The success of the BWT lies in its pattern matching algorithm known as backward search, which is not only near-optimal in the RAM model, but also runs directly on a compressed representation of the input string. More recently, the backward search has been generalized to Wheeler deterministic finite automata (DFAs), a subclass of standard DFAs, without losing its near-optimal time efficiency. Similarly to the case of strings, this pattern matching algorithm for Wheeler DFAs has found applications in bioinformatics, where researchers have shown that specific pangenome graphs of human chromosomes can be transformed into Wheeler DFAs and consequently indexed using this strategy. However, this BWT-based index on Wheeler DFAs inherited a significant drawback from the original backward search, namely the high number of I/O operations triggered during the algorithm execution, which are in the worst-case lower-bounded by the length of the pattern. In this paper, we address this limitation by proposing the first cache-friendly algorithm specifically designed for Wheeler DFAs. Our new data structure reduces the number of I/O operations by employing a strategy analogous to the suffix array: it interleaves a binary search with fast sequential scans of the automaton. We empirically validate this new indexing strategy by running our algorithm on real-world Wheeler pangenome graphs. We show that while our data structure can use up to 15 times the space required by the backward search, it can also be 500 times faster and able to process a single character of the pattern in less than 3 ns.

0

math.CO 2026-07-03

Bounded row treewidth allows unbounded geodesic treewidth

by Laura Merker, Lena Scherzer +1 more

Separating Geodesic Structure and Product Structure

Graphs of bounded row treewidth can require arbitrarily large geodesic treewidth; deciding geodesic treewidth 1 for treewidth-2 graphs is in

abstract click to expand

The geodesic treewidth of a graph $ G $ is the smallest $k$ for which there is a partition $\mathcal{P}$ into geodesics such that $G/\mathcal{P}$ has treewidth $k$, where $G/\mathcal{P}$ is obtained from $ G $ by contracting each part of $ \mathcal{P} $. Based on this notion, row treewidth was developed and is defined for a graph $ G $ as the smallest $ k $ such that $ G \subseteq H \boxtimes P $ for some graph $ H $ of treewidth $ k $ and a path $ P $. Equivalently, the row treewidth of a graph $ G $ is the smallest $ k $ for which there is a partition $ \mathcal{P} $ into disjoint unions of geodesics that are aligned with respect to some layering such that $ G/\mathcal{P} $ has treewidth $ k $. We separate the two notions by showing that bounded row treewidth does not imply bounded geodesic treewidth and by presenting a polynomial-time algorithm to decide whether a graph of treewidth 2 has geodesic treewidth 1, which is known to be NP-hard for row treewidth [Biedl, Eppstein, Ueckerdt, 2025]. More generally, we provide an algorithm to decide whether a given graph has geodesic treewidth at most $ d $ that is XP in the treewidth, whereas there is no such algorithm for row treewidth, unless P = NP [Biedl, Eppstein, Ueckerdt, 2025]. On the other hand, we show that computing the geodesic treewidth is NP-hard and that every graph with geodesic treewidth 1 has bounded row treewidth. Moreover, we improve the best known lower bound on the geodesic treewidth of planar graphs to 5.

0

cs.DS 2026-07-03

Courcelle theorem refined to ETH-tight variable counts per block

by Daniel Lokshtanov, Fahad Panolan +3 more

Fine-Grained Bounds for Courcelle's Theorem

The running time now tracks the exact number of first- and second-order variables inside each quantifier alternation rather than alternation

abstract click to expand

Courcelle's theorem states that there exists an algorithm that takes as input a graph $G$ of treewidth at most $t$ and a MSO formula $\phi$, and determines whether $G$ satisfies $\phi$ in time $f(\phi,t) \cdot n$. It is folklore that the the function $f$ contains a tower of exponentials whose height depends as a linear function of the number of quantifier alternations of the input formula $\phi$. A classic reduction of Frick and Grohe shows that, assuming the Exponential Time Hypothesis (ETH), the linear growth of the height of the tower is unavoidable. Nevertheless, there is still a huge gap between existing upper and lower bounds -- after all, there is quite a difference between a single exponential and a double exponential running time. In addition, this only gives us a very coarse understanding in the time complexity of Courcelle's theorem. In this paper, we prove a fine-grained version of Courcelle's theorem with nearly ETH-tight dependence on the treewidth parameter $t$ and the quantifier structure of $\phi$ (specifically, the number of first order and second order variables in each quantifier alternation block).

0

cs.DS 2026-07-03

Sampling estimates silhouette of k-clustering to additive O(ε) error

by Ilie Sarpe, Federico Altieri +3 more

Scalable and Distributed Silhouette Approximation

The first provable method needs only O(nkε^{-2}ln(nk/δ)) distances and extends to constant-round MapReduce and MPC implementations.

abstract click to expand

The silhouette is one of the most widely used measures to assess the quality of a $k$-clustering of a dataset of $n$ elements. Its evaluation requires no information beyond the clustering assignment. In addition, the silhouette is extremely easy to interpret, providing a score to measure the quality of a clustering as a whole or for each element. The exact computation of the: (i) silhouette of each element of a dataset; and (ii) the global silhouette of the clustering; require $\Theta(n^2)$ distance calculations, under general metrics. The quadratic complexity $\Theta(n^2)$ is extremely prohibitive, especially on massive modern datasets. Surprisingly, existing approximate methods using $O(n^2)$ distance calculations are heuristics not offering provable and controllable guarantees on the quality of their results. We introduce the first rigorous and efficient algorithms to estimate: (i) the (local) silhouette of each element of a dataset; and (ii) the (global) silhouette; of any metric $k$-clustering. Our methods, based on sampling, perform $O(nk\varepsilon^{-2}\ln (nk/\delta))$ distance computations, and provide estimates with additive error $O(\varepsilon)$ with probability at least $1-\delta$. That is, parameters $\varepsilon$ and $\delta$ in $(0,1)$ control the trade-off between accuracy and efficiency. We also introduce a scalable and distributed design of our methods for the MapReduce and Massively Parallel Computing (MPC) frameworks. Our distributed algorithms use a constant number of rounds and sublinear local memory. Finally, we perform extensive experiments against state-of-the-art approaches. The results show that our new techniques yield the best trade-off between accuracy and efficiency for both local and global silhouette estimation. In addition, our methods scale efficiently to massive datasets for which an exact computation of the silhouette is not practical.

0

cs.DS 2026-07-03

Subquadratic diameter algorithm reaches real-weighted minor-free digraphs

by Da Wei Zheng

Real-weighted Diameter and Eccentricity of Minor-free and Bounded VC-dimension Graphs in Truly Subquadratic Time

Randomized reduction lifts VC-dimension methods past the integer-weight barrier for K_h-minor-free graphs.

abstract click to expand

We present the first truly subquadratic time algorithm to compute diameter and eccentricity in real-weighted directed graphs with constant distance VC-dimension and strongly sublinear-sized balanced separators. This runs in $O(n^{2-1/(2h-2)}\textrm{polylog}(n))$ time for real-weighted $K_h$-minor-free digraphs. Prior to this work, truly subquadratic time computation of diameter was only known for real-weighted planar graphs, while extensions to broader classes like minor-free graphs were restricted to unweighted settings. In particular, existing algorithms that use VC-dimension [Ducoffe, Habib, Viennot; SICOMP 2022][Le, Wulff-Nilsen; SODA 2024][Chan, Chang, Gao, Le, Kisfaludi-Bak, Zheng; FOCS 2025] work with small integer weights, but do not naturally generalize to real weights. We overcome this barrier by introducing a randomized search-to-decision reduction, demonstrating that VC-dimension is a sufficiently powerful tool in the real-weighted regime.

0

cs.DS 2026-07-03

Telephone broadcast gets single-exponential FPT for vertex cover

by Édouard Bonnet, Carl Feghali +1 more

Faster Parameterized Broadcasting

Turing reduction to edge-weighted b-matching improves prior cubic and quadratic exponents to O(vc log vc) and O(k log k).

abstract click to expand

Given a connected graph $G$ and a source $s \in V(G)$, what is the smallest number of rounds necessary for all vertices of $G$ to receive a message initially only held by $s$, where at each round every informed vertex passes the message to one of its neighbors? This problem is called Telephone Broadcast and is suprisingly hard: it remains NP-hard on cycles intersecting at a single shared vertex, in particular, graphs of pathwidth 2 with a linear feedback vertex set of size 1, as well as on graphs with treedepth at most 6 [Egami et al.; MFCS '25]. Vertex cover number, vertex integrity, and distance to clique are among the few parameters for which Telephone Broadcast is fixed-parameter tractable. There is a $2^{\mathcal{O}(\mathrm{vc}^3)} n^{\mathcal{O}(1)}$-time algorithm parameterized by vertex cover number $\mathrm{vc}$ [Fomin, Fraigniaud, Golovach; TCS '24], a double-exponential algorithm parameterized by vertex integrity $\mathrm{vi}$, and a $2^{\mathcal{O}(k^2)} n^{\mathcal{O}(1)}$-time algorithm parameterized by distance to clique $k$ [Egami et al.; MFCS '25]. In this paper, we give improved parameterized algorithms for Telephone Broadcast with running times $2^{\mathcal{O}(\mathrm{vc} \log \mathrm{vc})} n^{\mathcal{O}(1)}$, $2^{\mathcal{O}(\mathrm{vi}^2 \log \mathrm{vi})} n^{\mathcal{O}(1)}$, and $2^{\mathcal{O}(k \log k)} n^{\mathcal{O}(1)}$. The main ingredient that makes our algorithms faster is a Turing reduction to edge-weighted $b$-Matching.

0

cs.DS 2026-07-03

Algorithm matches unordered tree patterns in O(N max{nD^{3/2},S}) time

by Shintaro Matsushita, Takayoshi Shoudai +1 more

Efficient Pattern Matching in Unordered Term Tree Patterns with Height Constraints

Height-constrained variables let the method handle trees where child order does not matter, such as syntax trees and chemical structures.

abstract click to expand

Unordered trees appear in applications where the order among child vertices is insignificant, such as abstract syntax trees and chemical structures. To describe patterns in such trees, we propose unordered term tree patterns, which employ height-constrained variables that restrict trunk length and subtree height. We formalize the pattern matching problem between an unordered term tree pattern and an unordered tree, and present an $O(N \cdot \max\{nD^{3/2}, \mathcal{S}\})$-time algorithm, where $n$ and $N$ are the numbers of vertices in the pattern and tree, $D$ is the maximum vertex degree, and $\mathcal{S}$ is the sum of trunk constraints. Computational results show that the algorithm runs efficiently in practice.

0

cs.CC 2026-07-03

Clause substitution creates local blind spot in K-SAT

by Wen Fang, Xianxian Li +4 more

Self-Referential K-SAT and the Finite Analogue of G\"odel's Incompleteness Theorem

Indistinguishable SAT/UNSAT pairs force wide clauses in Resolution and push proof size toward 2^N.

abstract click to expand

Self-reference and solution independence are core properties underlying intractability. This paper establishes a finite combinatorial analogue of G\"odel's incompleteness theorems within Boolean $K$-SAT. While standard random $K$-SAT has assignment correlations that disrupt solution independence, we resolve this via a logarithmic-width ensemble ($K = O(\log N)$). Here, satisfying assignments converge to a Poisson distribution, letting unsatisfiable and uniquely satisfiable formulas coexist. By executing a single-clause substitution conditioned on the unique solution, we construct structurally irreducible SAT/UNSAT pairs that are indistinguishable via local evaluation. Using algorithmic information theory and Shannon channels, we prove that deductive pipelines restricted to a sublinear window suffer from an informational blind spot, forcing a descriptive lower bound of $K(\mathcal{A}) \geq \Omega(N^{1-\delta})$. This deficit forces any Resolution refutation of the UNSAT instance to utilize wide clauses ($w(\pi) \geq \Omega(N^{1-\delta})$), triggering an exponential proof-tree explosion ($S(\phi) \geq \exp(\Omega(N^{1-2\delta}))$). As $\delta \rightarrow 0^+$, this bound converges to the worst-case $2^N$ threshold, reframing the Strong Exponential Time Hypothesis (SETH) as a direct projection of G\"odel incompleteness onto finite computation. We diagnose the decades-long stagnation in complexity theory. Transitioning from Turing's class separation to a G\"odelian paradigm of instance indistinguishability, we introduce a multi-dimensional comparative framework that contrasts these two historical lineages across distinct perspectives. The self-referential hardness exhibits physical invariance: it precludes quantum shortcuts due to the necessity of global semantic analysis and delineates a scaling bottleneck for machine learning architectures operating on lossy, local compression.

0

cs.DS 2026-07-03

CDAWG built from BWT-runs in output-sensitive time

by Yuta Tsuruzono, Hiroki Arimura +1 more

Output-Sensitive Construction of CDAWGs from BWT-Runs

Algorithm uses compressed suffix tree to produce CDAWG with e_L edges in O(e_L log n log(n/r)) time and O(r log(n/r)+e_L) space.

abstract click to expand

The compact directed acyclic word graph (CDAWG) of a string can be viewed in two equivalent ways: as the edge-compacted DAWG of the string, and as the DAG obtained from the suffix tree by merging the nodes whose subtrees are isomorphic. By exploiting these two views in opposite directions, we show how to build, for the (reversed) input string of length $n$, the CDAWG with $e_L$ edges in $O(e_L\log n\log(n/r))$ time with $O(r\log(n/r)+e_L)$ words of working space, provided that the fully functional compressed suffix tree of Gagie, Navarro, and Prezza of size $O(r\log(n/r))$ is available. Here, $r$ denotes the number of BWT-runs of the input string.

0

cs.DS 2026-07-03

Path copying on AVL trees enables persistent string LCE

by Taiki Kaneda, Hiroki Arimura +1 more

Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars

FeAVL achieves O(log n) worst-case time for updates and structural ops with only O(log n) new nodes per change.

abstract click to expand

We study fully persistent dynamic strings with equality and longest common extension (LCE) queries. Straightforward full persistence is problematic for the splay-based FeST structure, since the same unbalanced past version can be reused indefinitely and the usual amortized analysis no longer applies. We give a fully persistent dynamic LCE structure, called FeAVL, based on path copying over AVL trees. For an operation involving string(s) of total length $n$, it supports split, concatenate, and single-character updates in worst-case $O(\log n)$ time, equality in worst-case $O(\log n)$ time w.h.p., and LCE in worst-case $O(\log n+\log^2\ell)$ time w.h.p., where $\ell$ is the answer; each update creates only $O(\log n)$ new permanent nodes. We also give a grammar-compressed instantiation via AVL grammars: starting from an initial grammar of size $g_0$, after $U$ updates, the total number of permanent grammar nodes is $O(g_0+I+U\log n_{\max})$, where $I$ is the number of inserted fresh characters and $n_{\max}$ is the maximum string length appearing during the update sequence.

0

cs.DS 2026-07-03

Unate distributions need n to the 3/2 samples for uniformity tests

by DaeHo Lee, Shivam Nadimpalli +2 more

Testing Unate Distributions

This is more samples than needed for monotone distributions but far less than the quadratic cost of naive reduction to monotone case.

abstract click to expand

We initiate the study of *unate distributions* over $\{\pm1\}^n$ -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-studied questions for monotone distributions: - Uniformity Testing of Unate Distributions: We show that $\widetilde{\Theta}(n^{3/2})$ samples are sufficient and necessary, in contrast to the $\widetilde{\Theta}(n)$ sample complexity of the analogous problem for monotone distributions (Rubinfeld and Servedio, STOC 2005; Adamaszek, Czumaj, and Sohler, SODA 2010). - Unateness Testing of Arbitrary Distributions: We give a tester that uses $\widetilde{O}(n^{3/2})$ conditional samples in the subcube conditional model. On the other hand, every tester that draws conditional samples in a similar fashion, namely from $O(1)$-dimensional subcubes, must have an $\widetilde{\Omega}(n^{2/3})$ complexity. In the same model, the complexity of monotonicity testing was recently shown to be $\widetilde{\Theta}(n)$ (Chakrabarty et al., STOC 2025). Our algorithms for both problems significantly outperform the naive approach of reducing to the monotone case, which would incur $\Omega(n^2)$ sample complexity. Our uniformity tester relies on a subroutine that "weakly" learns the hidden orientations of a unate distribution, together with a new correlation bound for these estimates. Both tools may be of independent interest in studying monotonicity and unateness over $\{\pm1\}^n$.

0

cs.DS 2026-07-02

Max entropy TSP algorithm achieves 10/7 ratio on cycle cut instances

by Billy Jin, Nathan Klein +1 more

Maximum Entropy is a 10/7-Approximation Algorithm for the TSP on Half-Integral Cycle Cut Instances

The bound applies even on instances where the subtour LP gap reaches 4/3 and the algorithm can reach 11/8.

abstract click to expand

One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the Subtour LP relaxation of the TSP is equal to $\frac{4}{3}$. For 40 years, the best known upper bound was $1.5$, due to Wolsey. Recently, Karlin, Klein, and Oveis Gharan showed that the max entropy algorithm for the TSP gives an improved bound of $1.5 - 10^{-36}$. In this paper, we show that the maximum entropy algorithm is a $\frac{10}{7}$-approximation for half-integral cycle cut instances of the TSP. This class of instances contains examples which demonstrate the subtour LP has an integrality gap of at least $\frac{4}{3}$, as well as examples showing that the performance of the max entropy algorithm is no better than $\frac{11}{8}$. We note that in the authors recently gave an algorithm upper bounding the integrality gap of this class of instances by $\frac{4}{3}$, so this work does not (and could not) provide an improved bound on the integrality gap. However, since there is no reason to believe that the analysis of the maximum entropy algorithm on general instances is tight, our work provides hope (and potentially direction) for improved analysis on other instance classes.

0

cs.DS 2026-07-02

Asymmetric price tuples allow near-optimal online trading ratios

by Gagan Aggarwal, Anupam Gupta +2 more

Asymmetric Trading Prophets

Competitive ratios reach 1 minus Theta(log B0 over sqrt(B0)) for i.i.d. cases and improve further when buy equals sell.

abstract click to expand

The "Trading Prophet" problem challenges an online trader to maximize its profit by buying and selling assets under stochastic prices and capacity constraints, competing against an offline prophet with full foresight. In previous work, each arriving asset was assumed to have a single price $p_t$, and the trader was allowed to either buy a copy at this price (subject to having available capacity), or sell a copy (if it already held at least one copy in hand). However, this abstraction can fail to capture the structural asymmetry of decentralized dealer-based markets, where buying and selling opportunities could be distinct, and driven by individual preferences. To address this, we introduce the Asymmetric Trading Prophets problem, where at each timestep the trader observes a price tuple $(b_t, s_t)$ -- representing the cost to buy, and the revenue from selling at this timestep. Importantly, the $(b_t,s_t)$ tuple could be potentially arbitrarily correlated. We provide the first competitive analysis for this asymmetric trading prophets problem, characterizing the achievable profit based on the trader's capacity $B$ and initial inventory $B_0$. For the unit-capacity case of $B=1$, we design online algorithms that achieve constant competitive ratios for both i.i.d. and non-i.i.d. distributions on the price tuples, when the trader has one initial copy ($B_0=1$). For the general capacity case where $B$ can be large, we give algorithms for i.i.d. distributions that achieve a competitive ratio of $1 - \Theta(\log B_0/\sqrt{B_0})$. Finally, for the symmetric case (where the price tuple satisfies $b_t=s_t$), we improve this to get a competitive ratio of $1 - O(\log B/\sqrt{B})$, demonstrating that the performance approaches optimality as the capacity increases. We show that both ratios are tight up to a logarithmic factor.

0

cs.DS 2026-07-02

The paper gives a black-box reduction that converts any fast algorithm for multiplying…

by Karl Bringmann, Nick Fischer +1 more

Robustifying Sparse Matrix Multiplication

Any T(n, m_in, m_out) algorithm converts to one that outputs the k largest entries in Õ(T(n, m_in, k)) time.

abstract click to expand

In the seminal sparse matrix multiplication problem the goal is to compute the product of two $n \times n$ matrices when the matrices are sparse, i.e., when the number of nonzeros in the input matrices $m_{in}$ and/or the number of nonzeros in the output matrix $m_{out}$ are much smaller than $n^2$. In this paper, we explore the generalized problem of (approximately) computing the $k$ largest output entries, with an approximation error dependent solely on the smaller entries -- from the viewpoint of sparse recovery, this can be seen as a robust variant of sparse matrix multiplication. Despite the substantial research dedicated to sparse matrix multiplication, almost no existing algorithms are robust in this sense. The one exception is Pagh's algorithm in time $\widetilde O(m_{in} + nk)$ [ITCS'12], and it remained open whether other algorithms can be similarly made robust. Our principal contribution is a black-box reduction from robust sparse matrix multiplication to conventional sparse matrix multiplication with only polylogarithmic overhead. Specifically, we show that any sparse matrix multiplication algorithm with running time $T(n, m_{in}, m_{out})$ can be transformed into a robust algorithm running in time $\widetilde O(T(n, m_{in}, k))$. This reduction leverages an extensive toolkit from sparse recovery, and intriguingly, also involves solving a knapsack-type problem. By plugging in the state-of-the-art algorithm for sparse matrix multiplication by Abboud, Bringmann, Fischer, and K\"unnemann [SODA'24], we achieve significantly improved bounds such as $O((m_{in} + k)^{1.346})$. Notably, in the regime where $k \geq m_{in}^{1.762}$, our reduction culminates in an almost-optimal $k^{1+o(1)}$-time algorithm.

0

cs.DS 2026-07-02

Hypergraph components found with O(n) cut queries

by Deeparnab Chakrabarty, Hang Liao

Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles

Independent families bypass the identifiability barrier that blocks exact edge reconstruction.

abstract click to expand

We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal $O(n)$-query connectivity algorithms, hypergraphs face a fundamental identifiability barrier in that distinct hypergraphs can share identical cut-profiles, making exact edge learning impossible in general, a primitive crucial in the graph connectivity algorithms. We first present a zero-error randomized algorithm that identifies the connected components of any weighted hypergraph using $O(n)$ expected queries, matching the $\Omega(n)$ lower bound. This approach bypasses the reconstruction barrier by introducing the notion of ``independent families'' -- vertex subpartitions that do not share hyperedges -- and iteratively coarsening them using auxiliary weighted graph connectivity techniques [Liao-Chakrabarty, 2024]. Second, we demonstrate that the impossibility of exact learning depends on hyperedge parity. For even-parity hypergraphs, we show that the structure is reconstructible using a M\"obius transform on the CUT function to implement binary-search-style vertex identification. This yields deterministic algorithms for obtaining $k$-connectivity certificates for $r$-bounded even hypergraphs in $\tilde{O}_r(kn)$ queries. Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic $\tilde{O}(kn^{1.5})$ query complexity for $k$-connectivity. This significantly improves upon the general $\tilde{O}(n^2)$ bound derived via symmetric submodular function minimization.

0

cs.GT 2026-07-02

The paper develops online algorithms for allocating indivisible items with mixed positive

by Georgios Amanatidis, Giulio Giaconi +2 more

Online Fair Division Meets Reordering Buffers

With buffers of size linear in k and number of agents, algorithms achieve EF1 at every step and EF at most steps for personalized k-value…

abstract click to expand

We study the online fair division of indivisible mixed manna among agents with additive valuation functions. Under the standard online model, at each time step an indivisible item arrives; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated, before the arrival of the next item. At the same time, we also wish to maintain some fairness guarantee, and in this work we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item (EF1). Given the strong negative and the scarce positive results for this problem without additional assumptions, we augment our algorithms with buffers that can store and rearrange a limited number of items. This setting interpolates naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably sized buffers can achieve strong guarantees for personalized $k$-value instances, i.e., instances in which each agent assigns at most $k$ distinct values to items. In particular, we construct allocations that are EF1 at every time step and EF at most time steps, using a buffer of size linear in $k$ and in the number of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence of envy-free matchings that allocates most items. Finally, we extend our results to general additive valuation functions, with a dependence on the largest per-agent ratio between two values of the same sign, and we also identify limitations of our approach via impossibility results on the use of buffers with smaller size.

0

cs.GT 2026-07-02

The paper links fair allocation of conflicting items (graph vertices) to agents with…

by Ishay Haviv

Fair Allocation under Conflict Constraints via Strong Colorability

The paper introduces a hierarchy of strong chromatic number variants to characterize and algorithmically guarantee SD-EF1, EF1, and EF[1,1]…

abstract click to expand

In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, such that no two adjacent vertices are assigned to the same agent. We study this problem for agents with common preferences through the lens of three fairness criteria: stochastic-dominance envy-freeness up to one item for preference orders (SD-EF1), envy-freeness up to one item for monotone additive valuations (EF1), and envy-freeness up to one item from each side for general additive valuations (EF[1,1]). To do so, we introduce a hierarchy of variants of the strong chromatic number, a graph quantity introduced independently by Alon and Fellows in the early nineties. Our results reveal a close connection between fair allocation under conflict constraints and the first two levels of this hierarchy, providing a unified route to both existential and algorithmic results. For SD-EF1, we fully characterize the number of agents needed to guarantee a fair allocation of a given graph for every common preference order. For EF1 and EF[1,1], we provide analogous sufficient conditions, extending a result on path graphs due to Equbal, Gurjar, Igarashi, Kumar, Manurangsi, Nath, Saxena, Vaish, and Yoneda. We also show that, unlike in the SD-EF1 setting, the sufficient conditions for EF1 and EF[1,1] are not necessary in general. Our framework yields existential and algorithmic consequences in terms of the maximum degree. We obtain that every graph with maximum degree $\Delta$ admits SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least $3\Delta-1$. We further provide, for any $\varepsilon>0$, deterministic polynomial-time algorithms that find such allocations whenever the number of agents is at least $(3+\varepsilon)\Delta$. These guarantees strengthen earlier work by Barman and Viswanathan on equitable colorings.

0

cs.DS 2026-07-02

Wheeler determinization in linear time with given order

by Philip Bille, Inge Li G{o}rtz +2 more

Tighter Bounds for Wheeler Determinization

New algorithm runs in O(n_A + m_A + n_D + m_D) and is tight at Theta(n sigma) output size for any n and sigma

abstract click to expand

Given a Wheeler NFA $\mathcal{A}$, the Wheeler determinization problem is to construct a Wheeler DFA $\mathcal{D}$ that accepts the same language as $\mathcal{A}$. We use the notation $n_{\mathcal{A}},m_{\mathcal{A}}$ for the number of vertices and edges of $\mathcal{A}$, and equivalently $n_{\mathcal{D}},m_{\mathcal{D}}$ for $\mathcal{D}$. Alanko et al. [SODA 2020, Inf. Comp. 2021] show that we can solve this problem in $O(n_{\mathcal{A}}^3)$ time. In this paper, we show how to improve the running time to $O(n_{\mathcal{A}} + m_{\mathcal{A}} + n_{\mathcal{D}} + m_{\mathcal{D}})$ when given the Wheeler order of $\mathcal{A}$ (which can be computed in $O(m_{\mathcal{A}}\log n_{\mathcal{A}})$ with an algorithm by Becker et al. [ESA 2023]). Our running time is a factor $n_{\mathcal{A}}^2/\sigma$ faster than the state of the art, where $\sigma$ is the size of the alphabet. Furthermore, for $\sigma=O(1)$ we have the first linear time algorithm for this problem. We show that our bound is tight for sorted inputs with any combination of $n$ and $\sigma$, by giving a family of inputs for which our output $\mathcal{D}$ is minimum, and of maximum size $\Theta(n\sigma)$.

0

math.PR 2026-07-02

Expected load gap on cycles stays order sqrt(n)

by Dean Kraizberg, Ron Peretz

Sharp Bounds for Dynamic Averaging on Cycles

Dynamic averaging by random edge selection and averaging proves upper and lower bounds matching at sqrt scale.

abstract click to expand

We study a dynamic averaging process on the cycle $C_n$. At each discrete time, an edge is chosen uniformly at random, one unit of load is introduced, and the two endpoint loads are replaced by their common average after the new unit has been added. Starting from the zero configuration, we prove that the expected gap between the largest and smallest loads is $O(\sqrt n)$, uniformly in time. Building on the lower-bound argument of Alistarh, Nadiradze, and Sabour for the expected square of the gap, we further show that the expected gap is $\Omega(\sqrt n)$ in the long run. This confirms their conjecture that the expected gap is of order $\sqrt n$.

0

cs.DS 2026-07-02

Weighted girth approx matches unweighted for all k

by Avi Kadria, Liam Roditty +1 more

Tighter bounds for weighted and unweighted shortest cycle approximation

A 2k/3 approximation to shortest cycle length runs in Õ(m + n^{1+2/k}) time.

abstract click to expand

We study the problem of approximating the length of a shortest cycle in a given graph, known as the girth of the graph. The state-of-the-art approximation algorithms for unweighted graphs by Kadria et al. [SODA'22] and Roditty and Trabelsi [arXiv'25] achieve the following trade-off: for every integer $k\geq 2$, there is an $\tilde{O}(n^{1+2/k})$ time algorithm that achieves a $(2k/3)$-approximation for the girth in unweighted $n$-node graphs. The first result of this paper is to achieve the same trade-off for $m$-edge, $n$-node graphs with non-negative real edge weights: a $2k/3$-approximation algorithm running in $\tilde{O}(m+n^{1+2/k})$ time. The dependence on $m$ is unavoidable in weighted graphs. Our result improves on the work of Kadria et al.~[SODA'23] and Ducoffe [ICALP'19 and SIDMA'21], who were only able to achieve such a trade-off for some values of $k$. We also prove new fine-grained lower bounds for girth approximation and related problems in unweighted graphs.

0

cs.DS 2026-07-02

Linear space suffices for single-source mincut failure oracles

by Koustav Bhanja, Merav Parter +1 more

Space-Optimal Sensitivity Oracles for Single-Source Mincuts

New connections to connectivity carcasses match insertion-query performance while handling edge failures.

abstract click to expand

We study Single-Source Mincut Sensitivity Oracles: compact data structures that, when queried with an edge e, report those affected vertices whose mincut value to source $s$ changes upon the insertion or failure of e. Insertion queries were treated by Baswana, Gupta, and Knollmann [Algorithmica '22], who showed an extremely compact oracle with only O(n) space. In this work, we consider edge failure queries, which are of even greater interest, but far more challenging. The current-best approaches give O(n^2) space: either using n-1 fixed-pair oracles of O(n) space each, based on the Picard-Queyranne representation [MPS '80], or using the O(n^2) space all-pairs oracle by Baswana and Pandey [SODA '22]. -Our key result is an optimal O(n) space single-source mincut sensitivity oracle for edge failure queries. It reports the set of affected vertices in O(n) time, thus matching the state-of-the-art bounds for the insertion case. -Additionally, we provide oracles with near-optimal query times at the cost of increasing the space to O(n^{1.5}). They can determine if any given vertex is affected by an insertion/failure of an edge in O(log n) time, or reports all affected vertices in amortized O(\log^3 n) time per vertex. Such oracles of subquadratic space were previously unknown, even for insertion. Our main technical contribution is in establishing novel and intricate connections between two seemingly distant objects, representing two different families of mincuts. The first is the DAG representation of farthest mincuts to the source, which was the central tool introduced by Baswana, Gupta, and Knollmann. The second is the Connectivity Carcass for Steiner mincuts of Dinitz and Vainshtein [STOC '94], which generalizes well-known cactus representations of global mincuts. Our work demonstrates the relatively unexplored potential of the carcass beyond its obvious Steiner mincuts scope.

0

cs.DS 2026-07-02

O(n log n) algorithm reaches 4/3 approximation for parallel tasks

by Bennet Edler, Klaus Jansen +2 more

Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling

The method improves the prior (3/2)OPT + p_max bound and extends the 9/4 guarantee to all cluster counts.

abstract click to expand

In the problem of Parallel Task Scheduling (PTS), we are asked to schedule $n$ jobs, each with a fixed processing time and machine requirement, such that the completion time of the last job is minimized. Jansen and Rau (2019) presented an algorithm for PTS that achieves an approximation ratio of $(3/2)\text{OPT} + p_{\max}$. They additionally posed the open question whether an approximation ratio of $(4/3)\text{OPT} + p_{\max}$ is possible. In this work, we present such an algorithm with a running time of $O(n\log n)$. The problem of Multiple Cluster Scheduling (MCS) is a natural extension of PTS where we are given $N$ clusters each of $m$ machines to schedule jobs. Jansen and Rau (2019) adapted their PTS algorithm to MCS with the following results: (1) a 2 approximation, and (2) a near-linear 9/4 approximation if $N$ is divisible by 3. We improve the running time of their 2-approximation and generalize the 9/4 approximation to the general case. The 2-approximation for MCS is tight, since one cannot hope for an approximation ratio better than 2, unless P=NP [Zhuk, 2006]. In addition to our theoretical results, we implement our algorithm and show its practical applicability.

0

cs.DS 2026-07-02

Private continual counting needs Ω((log n)^{3/2}) error

by Konstantina Bairaktari, Kasper Green Larsen

The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

Lower bound matches binary tree upper bound, proving asymptotic optimality under approximate DP and tightest separation from hereditary disc

abstract click to expand

Private continual counting is a fundamental problem in differential privacy: given a binary stream of length $n$, where each $1$ corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. The standard algorithm is the binary tree mechanism, whose Gaussian-noise variant achieves expected $\ell_\infty$ error proportional to $\log^{3/2} n$ for approximate differential privacy. Whether this dependence on the stream length is necessary has remained a central open problem. In this work, we resolve the dependence on $n$ by proving that every differentially private mechanism for continual counting must incur expected $\ell_\infty$ error $\Omega(\log^{3/2} n)$. This shows that the binary tree mechanism is asymptotically optimal in the approximate-DP setting. As a consequence, we also obtain a largest-possible separation between hereditary discrepancy and private $\ell_\infty$ error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.

0

cs.DS 2026-07-02

APSP solved in O(n^{2.83} + ηn) time with detour predictions

by Adam Polak, Jonas Schmidt

Warm-Starting All-Pairs Shortest Paths with Predictions

Runtime improves over cubic whenever the number of prediction errors is polynomially below n squared.

abstract click to expand

One of the three key hypotheses of fine-grained complexity asserts that computing All-Pairs Shortest Paths (APSP) requires cubic time, up to subpolynomial factors, in the worst case. We initiate the study of APSP in the paradigm of algorithms with predictions, also known as learning-augmented algorithms. We propose an APSP algorithm that takes as additional input a \emph{prediction} (e.g., given by a model learned from similar instances seen in the past) consisting of sets of vertices causing the shortest \emph{detour} for each pair of vertices. The algorithm runs in time $\mathcal{O}(n^{2.83} + \eta n)$, where $\eta$ denotes the \emph{prediction error} defined as the number of pairs of vertices for which, informally speaking, the prediction was not sufficient to compute and certify optimality of the shortest path length. This is already subcubic when the prediction error is (polynomially) smaller than its maximum possible values $n^2$, i.e., whenever the prediction is at least slightly better than terrible. We build on the co-nondeterministic algorithm for the Exact Triangle problem by Chan, Vassilevska Williams, and Xu (STOC 2023), essentially enabling this algorithm to detect mistakes in the nondeterministic certificate and recover from them. Our result constitutes the first necessary step towards designing learning-augmented algorithms for problems with known fine-grained lower bounds conditioned on the APSP Hypothesis.

0

cs.DS 2026-07-02

Ordered local search hits k/2 + o(k) for k-matroid submodular max

by Neta Singer, Theophile Thiery

Submodular Maximization over Many Matroids via Ordered Local Search

The algorithm processes elements by marginal value and swaps when gain exceeds a k-dependent threshold, matching the unweighted optimum asym

abstract click to expand

Given a monotone submodular function, we consider the problem of finding a maximum-valued set in the intersection of $k$ matroids. Our main result is a polynomial time local search based algorithm achieving a $\frac{k}{2} + o(k)$ approximation guarantee. This asymptotically matches the best-known guarantee of $\frac{k}{2} + \epsilon$ in the unweighted setting by Lee, Sviridenko, and Vondr\'ak (2009). Prior to this work, the state-of-the-art was a $\frac{\ln(4)k}{1+\ln(2)} + o(k)$-approximation algorithm obtained by Feldman and Ward (2026). Our approach extends to Matroid $k$-Parity yielding the same approximation guarantee. In contrast to the weight bucketing approach underlying the recent advances of Singer and Thiery (2025) and Feldman and Ward (2026), our algorithm processes elements greedily in decreasing order of marginal value and searches for sufficiently profitable swaps, whose gain exceeds a parameter $\alpha$ given as a function of $k$. We further combine this idea with the weight bucketing approach to obtain improved guarantees for weighted $k$-Set Packing. Our second main result is a $\frac{\ln(4)k}{3} + o(k)$-approximation algorithm for weighted $k$-Set Packing, improving on the state of the art $\frac{k}{2.00561} + O(1)$-approximation by Neuwohner (2023).

0

cs.LG 2026-07-02

Parallel sampling cuts discrete diffusion complexity to log scale

by Yu Yao, Huanjian Zhou +3 more

Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling

Reformulates τ-leaping with Picard iteration to reach O(log(d log S) log d) NFE while matching original sample quality.

abstract click to expand

Discrete diffusion models are widely used for learning and generating discrete distributions. As the generation process is inherently sequential, the acceleration of sampling is of significant importance. In this work, we parallelize the mainstream $\tau$-leaping algorithm for absorbing discrete diffusion in a Continuous-Time Markov Chain (CTMC) framework. By leveraging the continuous-time stochastic integral form of the $\tau$-leaping algorithm and the Picard iteration method, we achieve parallel-in-time sampling acceleration and provide a proof of exponential-factorial convergence for our algorithm. We improve the overall time complexity of $\tau$-leaping under absorbing settings from ${\mathcal{O}}(d \log S)$ to ${\mathcal{O}}(\log (d\log S)\cdot \log d)$ with respect to NFE. Empirically, our method shows consistent acceleration across synthetic and real-data settings. The new sampler achieves at most $7$--$9\times$ runtime speedup for synthetic distribution, and maintains the same quality with $50\%$ fewer NFE and $1.45$--$1.86\times$ runtime speedups in image/text tasks on a single GPU. Our research expands the potential of discrete diffusion models for efficient parallel inference, with broader implications for applications such as molecular structure and language generation.

0

cs.DS 2026-07-02

Link-cut suffix tree computes all maximal closed substrings online in O(n log n)

by Hiroki Shibata, Haruki Umezaki +3 more

Online computation of maximal closed substrings

The structure tracks rightmost suffix occurrences to report every maximal closed substring as each new character arrives, matching the worst

abstract click to expand

A non-empty string is closed if its length is one or its longest border appears exactly twice in the string. An occurrence of a closed substring is a maximal closed substring (MCS) if it cannot be extended to the left or to the right while preserving closedness. MCSs can be regarded as a general class of maximal repetitive structures including runs. In this paper, we study the computation of MCSs of a string given in an online manner, where one character is appended to the string at a time. Our algorithm detects newly formed MCSs after each append operation by using the rightmost previous occurrences of suffixes. To support this efficiently, we introduce the link-cut suffix tree (LCST), a novel data structure combining an online suffix tree with a link-cut tree. The LCST maintains rightmost occurrence information for substrings represented in the suffix tree in $O(n \log n)$ total time and $O(n)$ space, where $n$ is the length of the input string. Using the LCST, we obtain an $O(n \log n)$-time online algorithm for computing all MCSs, which is worst-case optimal. As further direct applications of the LCST, we obtain online algorithms for rightmost LZ77 factorizations and most recent match queries.

0

cs.DS 2026-07-02

Size-based delays encode matching as metrical task systems on 2^n metrics

by Junhao Gan, Xiao Sun +1 more

Online Matching with Size-Based and Convex Delays

Settling deterministic competitive ratios up to constants and giving O(1) algorithms for polynomial convex delays with f'(0) greater than ze

abstract click to expand

We study the online min-cost perfect matching with delay (MPMD) problem where $m$ requests arrive in a metric space of $n$ points. In MPMD, an algorithm can choose to match a request or to delay, and the objective is to minimise the sum of connection and delay costs. The connection cost of a match is the distance between the locations of two matched requests in the metric, and the increase of the delay cost is a function of the set of unmatched requests at every moment. In this paper, we study two different types of delay functions, size-based (MPMD-Size) and convex delays (MPMD-Convex). The study of MPMD-Size was initiated by Deryckere and Umboh (APPROX/RANDOM 2023) where the instantaneous delay increment is a non-negative monotone function of the number of unmatched requests. Our bounds are in terms of $n$, as opposed to Deryckere and Umboh's bounds that depend on $m$. Our results settle the deterministic competitive ratio (up to constants). At the heart of these results is a succinct encoding scheme of MPMD-Size on a given $n$-point metric as a metrical task system problem on a $2^{n-1}$-point metric. We also consider MPMD-Convex proposed by Liu et al. (ISAAC 2018) where the delay cost incurred by each request is a uniform convex delay function of the time difference between its arrival time and the moment that it is matched by the algorithm. They focused on delay functions $f$ that are unbounded, non-decreasing, continuous, and satisfy $f(0)=f'(0)=0$, and showed that the deterministic competitive ratio is $\Omega(n)$ for $n$-point uniform metrics. We show that, surprisingly, when $f$ is a non-negative, monotone polynomial with $f'(0)>0$, there is an $O(1)$-competitive deterministic algorithm for uniform metrics. Our result completes our understanding of MPMD-Convex on uniform metrics for a broad class of functions.

0

cs.DS 2026-07-02

Longest implicit suffix map folds to explicit leaves in O(1)

by Toshiharu Minematsu, Shunsuke Inenaga

Efficient LCE Queries and Lexicographic Minimizers on Sliding Suffix Trees

Sliding-window suffix trees gain amortized constant shifts and worst-case constant LCE plus fast minimizers on constant alphabets.

abstract click to expand

We study longest-common-extension (LCE) queries and lexicographic minimizer maintenance on the suffix tree of a sliding window. The main difficulty is that a sliding suffix tree is maintained in an implicit Ukkonen-style form: some suffixes of the current window are not represented by leaves. We show that the longest implicit (i.e. non-leaf) suffix induces a periodic representative map that folds every implicit suffix to an explicit suffix leaf in constant time. Combined with leaf pointers [Leonard et al., PSC 2026] and a dynamic LCA data structure [Cole & Hariharan, SICOMP 2005], this yields a linear-space data structure with amortized constant-time window shifts and worst-case constant-time LCE queries over a constant-size alphabet. For minimizers, the LCE structure gives a direct exact solution, but it uses more machinery than fixed-depth comparisons require. We therefore give an alternative LCE-free algorithm that reports minimizers in constant time per window shift, which is built on BP-linked suffix trees [Sumiyoshi et al, SPIRE 2024] and a standard order maintenance data structure (e.g. [Bender et al., ESA 2002]).

0

math.OC 2026-07-02

Local optima reach half the revenue of best randomized assortment policies

by Mikhail Fadin, Huseyin Topaloglu

Killing the Case for Randomization in Dynamic Assortment Optimization

De-randomization shows deterministic sequences match sampling performance exactly, so local search suffices for strong guarantees.

abstract click to expand

One of the traditional approaches for constructing approximate policies for dynamic assortment optimization problems is to use sampling-based inventory-agnostic policies. Such policies are called sampling-based, as they sample an assortment of products from a fixed distribution at each time period to offer to a customer of each type. Such policies are called inventory-agnostic, as the sampled assortments may include products without remaining inventories, so if a customer chooses a product without remaining inventories, then she leaves without a purchase. Inventory-agnostic nature of a policy is not a concern, because it is known that if the policy samples an assortment that includes products without remaining inventories, then dropping the products without remaining inventories does not degrade the performance. However, sampling-based nature of a policy is a concern, because sampling brings another source of uncertainty in the performance. In this paper, we give an algorithm to de-randomize any sampling-based inventory-agnostic policy, so the de-randomized policy offers a deterministic sequence of assortments within the support of the original policy without degrading the performance. Furthermore, we give a variation of our de-randomization algorithm that searches for a deterministic sequence of assortments beyond the support of the original policy. We show that we can implement the latter variation efficiently as long as we can solve the static assortment optimization problem under the choice model governing the choice process of the customers. As our crowning technical contribution, we study locally-optimal deterministic policies, where changing any single one of the assortments in the policy does not improve the total expected revenue. We show that any locally-optimal policy has a performance guarantee of 1/2 - epsilon when compared with the best sampling-based policy.

0

math.CO 2026-07-01

Chromatic Sum complexity fully classified on forbidden graph classes

by Clément Dallard, Daniël Paulusma +1 more

Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs

New NP-completeness result on planar subdivisions completes the map for all minor-free and H-free classes.

abstract click to expand

The Chromatic Sum problem asks, given a graph $G$ and an integer $k$, whether $G$ admits a colouring $c$ with sum $\sum_{v\in V}c(v) \leq k$. We study the complexity of Chromatic Sum on graph classes defined by some set of forbidden graphs. First, we show that three known frameworks fully classify the complexity of Chromatic Sum on $HH$-minor-free graphs and $HH$-topological-minor-free graphs for any set of graphs $HH$, and on $HH$-subgraph-free graphs for any finite set of graphs $HH$. To show this, we prove a new NP-completeness result for Chromatic Sum on certain subdivisions of planar subcubic graphs. Next, we consider other containment relations. We formalise a novel framework of problems that are NP-complete for planar graphs as well as for graphs of bounded independence number. For every problem in this framework, we obtain an almost complete complexity classification on $H$-induced-minor-free graphs, $H$-induced-topological-minor-free graphs, and $H$-free graphs for every graph $H$. We show that Chromatic Sum belongs to this framework, as do several other problems. We also define a more fine-grained framework for the induced subgraph relation. We apply this to obtain a complete complexity classification for Chromatic Sum on $H$-free graphs, as well as for several other problems. We justify the choice of this framework by proving that Chromatic Sum is NP-complete for graphs of clique-width at most $3$. This result complements a known polynomial-time result for graphs of clique-width at most $2$.

0

cs.LG 2026-07-01

Distributionally Robust Linear Regression With Block Lewis Weights

by Naren Sarayu Manoj, Kumar Kshitij Patel

The reduction yields a (1+ε) solution with Õ(min(rank(A),m)^{1/3} ε^{-2/3}) linear solves and matches ℓ_∞ regression bounds.

abstract click to expand

We present an algorithm for the group distributionally robust (GDR) least squares problem. Given $m$ groups, a parameter vector in $\mathbb{R}^d$, and stacked design matrices and responses $\mathbf{A}$ and $\mathbf{b}$, our algorithm obtains a $(1+\varepsilon)$-multiplicative optimal solution using $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ linear-system-solves of matrices of the form $\mathbf{A}^{\top}\mathbf{B}\mathbf{A}$ for block-diagonal $\mathbf{B}$. Our technical methods follow from a recent geometric construction, block Lewis weights, that relates the empirical GDR problem to a carefully chosen least squares problem and an application of accelerated proximal methods. Our algorithm improves over known interior point methods for moderate accuracy regimes and matches the state-of-the-art guarantees for the special case of $\ell_{\infty}$ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.

0

cs.CC 2026-07-01

n^{γ/(log log n)^2} approx for MIS on twin-width 4 refutes ETH

by Édouard Bonnet, Maël Dumas +1 more

Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width

Nearly matches the existing n^{O(1/log log n)} approximation and holds even with a provided 4-sequence.

abstract click to expand

For every $\varepsilon > 0$, Max Independent Set admits a polynomial-time $n^\varepsilon$-approximation algorithm on $n$-vertex graphs of effectively bounded twin-width [Berg\'e et al., STACS '23]. The approximation factor actually obtained is more precisely $n^{O(1/ \log \log n)}$. Prior to the current paper, no approximation hardness was known for this problem, and the existence of a polynomial-time approximation scheme (PTAS) was repeatedly raised as an open question. We answer this question in a strong sense: We show that there is a constant $\gamma > 0$ such that a polynomial-time $n^{\gamma/ (\log \log n)^2}$-approximation algorithm for Max Independent Set on graphs of twin-width at most 4 would refute the Exponential-Time Hypothesis (ETH). This lower bound further holds if a 4-sequence is provided as part of the input. We show the same hardness of approximation for Min Coloring, which also has a nearly matching $n^{O(1/ \log \log n)}$-approximation algorithm on graphs of effectively bounded twin-width. We also clarify the parameterized complexity of $k$-Independent Set on graphs of bounded radius-$r$ merge-width when the range of $r$ is limited. There is a fixed-parameter tractable algorithm for $k$-Independent Set on graphs given with radius-$2^{O(k^2)}$ merge sequences of bounded width [Dreier and Toru\'nczyk, STOC '25]. We complement this result by showing that $k$-Independent Set is W[1]-hard on graphs given with radius-$o(k)$ merge sequences of bounded width. We further show that this result also holds for $k$-Dominating Set.

0

cs.DS 2026-07-01

Suffixient arrays computed in sublinear time

by Hiroto Fujimaru, Gonzalo Navarro +4 more

Computing Smallest Suffixient Arrays in Sublinear Time

Time drops below linear when alphabet is small and BWT has few equal-letter runs

abstract click to expand

A suffixient array is a novel data structure that, when combined with an index providing direct access on a text $T$, allows us to answer a variety of pattern matching queries. In this work, we show how to compute a smallest suffixient array for $T[1\dots n]$ in $O(\frac{n\log \sigma}{\sqrt{\log n}}+\min(r,\bar{r})\log^\epsilon n)$ time for any $\epsilon > 0$, where $\sigma$ is the alphabet size of $T$ and $r$ and $\bar{r}$ are the numbers of equal-letter runs of the Burrows-Wheeler transforms of $T$ and its reverse $\overline{T}$, respectively. This time complexity becomes sublinear when $\sigma$ is small enough and $\min(r,\bar{r})=o(\frac{n}{\log^\epsilon n})$, yielding an asymptotic improvement over state-of-the-art algorithms. We also present a series of connected algorithmic results.

0

cs.DS 2026-07-01

Temporal path cover size equals Lovász number under Dilworth promise

by Lapo Cioni, Sotiris Kanellopoulos +4 more

Temporal Path Covers: Dilworth Properties and Parameterized Complexity

The equality holds by promise, yielding polynomial-time algorithms; hardness results show vertex cover plus time-steps is needed for FPT.

abstract click to expand

The Minimum Temporal Path Cover (TPC) and Minimum Temporally Disjoint Path Cover (TDPC) problems were introduced by [Chakraborty, Dailly, Foucaud, Klasing, MFCS '24]. Both were shown to be NP-hard on temporal DAGs, while the latter is also NP-hard on temporal oriented trees. All tractable cases for T(D)PC established in that paper satisfy a temporal Dilworth property, namely that the size of the minimum T(D)PC is equal to the size of the maximum antichain. This raises a natural question: is T(D)PC polynomial-time solvable under the promise that the respective Dilworth property holds? In this work, we answer this question in the affirmative for both problems, proving in fact that, under the respective promise, the size of the minimum T(D)PC is exactly equal to the Lov\'asz number of the connectivity graph. In another direction, we establish parameterized algorithms and hardness results for TPC and TDPC. Our main result is that TPC is W[1]-hard parameterized by the deletion distance to linear forest even for temporal graphs with two time-steps, answering in the negative an open question by Chakraborty et al. about whether an XP algorithm parameterized by treewidth plus number of time-steps can be improved to FPT. On the other hand, we prove that an FPT algorithm does exist if the vertex cover number is used as parameter instead of the treewidth in the above parameterization. We complement this with a proof that including the number of time-steps in the parameter is necessary to yield tractability, as, otherwise, both TPC and TDPC remain NP-hard even for constant vertex cover size. Along the way, we establish various other para-NP-hardness results involving structural parameters such as the pathwidth and the maximum degree of the underlying graph.

0

cs.DS 2026-07-01

Monotone array completes in (1/2+o(1))n log n steps

by Vishesh Jain, Dylan King +1 more

The online monotone array completion problem

Matching bounds show optimal play halves coupon-collector time; with-replacement version reaches O(n sqrt(log n))

abstract click to expand

Consider the following online filling game. An array of length $n$ is initially empty. At each time step one observes an independent sample from $\mathrm{Unif}[0,1]$ and must either discard it or place it irrevocably into an empty position of the array, while preserving the constraint that the occupied entries are non-decreasing from left to right. Among all possible strategies, what is the optimal expected time required to fill the array? Let $v_n$ denote this optimal expected completion time. Our main result determines $v_n$ up to lower-order terms: \[ v_n=\left(\frac12+o(1)\right)n\log n. \] More precisely, no strategy, even if randomized and adaptive, can have expected completion time below $\left(\frac12-o(1)\right)n\log n$, while we provide an explicit deterministic strategy whose expected completion time is at most $\left(\frac12+o(1)\right)n\log n$. For comparison, the natural coupon-collector strategy, which partitions $[0,1]$ into $n$ equal intervals and reserves one array position for each interval, has expected completion time $(1+o(1))n\log n$. We also consider a with-replacement version of the game, in which previously placed entries may be overwritten. For this variant, we give a deterministic strategy with expected completion time $O(n\sqrt{\log n})$, thereby establishing a separation between the two models.

0

cs.DS 2026-07-01

Bounded-degree TSP now admits additive degree violation

by Jongseo Lee, Jaehyeok Kwak +1 more

Improved Algorithms for Bounded-Degree (Subset) Traveling Salesman Problems

New algorithm matches Christofides cost ratio and reduces violation to a fixed additive amount for both path and circuit versions.

abstract click to expand

We present improved algorithms for several bounded-degree traveling salesman problems. In the bounded-degree traveling salesman path problem (BDTSPP), given a weighted graph G=(V,E), two endpoints s and t, and degree bounds b_v for all v, the goal is to find a minimum-cost subgraph of G that admits an Eulerian s-t path and in which each vertex v has degree at most b_v. Since deciding feasibility is already NP-hard for this problem, previous work gave a bicriteria approximation algorithm. However, that algorithm provides only a multiplicative guarantee on the degree violation, and it was left open whether additive violation is possible. We answer this open question affirmatively by giving a new bicriteria approximation algorithm with additive degree violation. The cost approximation ratio is improved as well, now matching that of Hoogeveen's analysis of the Christofides-Serdyukov algorithm. This improvement relies on a new lemma that enables the use of a bounded-degree minimum spanning tree, rather than a bounded-degree Steiner tree, as a starting point for the algorithm. The lemma compares the cost and degrees of the tree against those of an integral optimum for the bounded-degree TSP at hand, rather than those of a fractional optimum. Our lemma brings improvement to the circuit version (BDTSP) as well: we give a bicriteria algorithm that matches the previous cost approximation ratio while reducing the additive degree violation to +2, which is best possible. Subset TSP is a generalization of the standard "all-vertices" TSP, in which only a specified subset of vertices is required to be visited. We present improvements for both the circuit and the path versions. For the subset path problem (BDSTSPP), we present the first bicriteria approximation algorithm with additive degree violation; for the subset circuit problem (BDSTSP), we give an improved cost approximation ratio.

0

cs.DS 2026-07-01

d-clique packing has n^{O(k^{d-1})} algorithm

by Narek Bojikian, Stefan Kratsch

Tight bounds for clique-packing parameterized by clique-width

The bound is tight under ETH even for partitioning into d-cliques, for any d at least 3.

abstract click to expand

In the $d$-Clique Packing problem, given a graph $G$ and an integer $t$, we need to decide whether $G$ contains a set of $t$ pairwise vertex-disjoint cliques of size $d$ each. This generalizes Triangle Packing and it is NP-complete for all $d\geq 3$. For each such $d$, we show how to solve the problem in $n^{O(k^{d-1})}$ time where $k$ is the clique-width of the graph (with a $k$-expression of $G$ given in the input). We complement this by showing that, assuming the Exponential-Time Hypothesis (ETH), there is no algorithm that solves the problem in $n^{o(k^{d-1})}$ time for any fixed $d\geq 3$, already for the special case of seeking a partition into cliques of size $d$. Our proof also entails W[1]-hardness of $d$-Clique Packing (and $d$-Clique Partition) parameterized by clique-width for each $d\geq 3$. Our work continues a series of results on ETH-tight bounds for fundamental graph problems started by Fomin et al.\ (SICOMP 2010+2014) who obtained tight bounds for Max-Cut and Edge Dominating Set.

0

cs.DS 2026-07-01

Poly-time token sliding on P4-tidy graphs

by Lucia Busolini, Mario Valencia-Pabon

Token sliding independent set reconfiguration on graphs with few P₄'s

Algorithms decide reachability for two families that generalize cographs by limiting induced P4s.

abstract click to expand

We consider the INDEPENDENT SET RECONFIGURATION problem under the Token Sliding rule. Let $I$ be an independent set of a simple undirected graph $G$. Suppose that each vertex of $I$ has a token placed on it. The tokens are allowed to be moved, one at a time, by sliding along the edges of $G$, so that after each move, the vertices having tokens always form an independent set of $G$. The problem we deal is to decide if we can transform $I$ into $I'$ through a sequence of steps, each of which involves substituting a vertex in the current independent set with one of its neighbours to obtain another independent set. This problem of determining if one independent set of a graph "is reachable" from another independent set of it is known to be PSPACE-hard even for split graphs, planar graphs, and graphs of bounded treewidth. Polynomial time algorithms have been obtained for certain graph classes like trees, interval graphs, claw-free graphs, bipartite permutation graphs, block graphs, and cographs. We present a polynomial time algorithm for the problem on $P_4$-tidy graphs and $(q,q-4)$-graphs, both families of graphs generalizing cographs.

0

cs.DC 2026-07-01

CRDTs decouple trust to exclude compromised updates without breaking causality

by Amos Brocco

Decoupling Trust in Byzantine CRDTs: Fine-grained Post-Compromise Handling without Breaking Causality

Fine-grained model separates sender identity from update content so replicas can drop malicious changes while keeping causal order intact.

abstract click to expand

Conflict-free Replicated Data Types (CRDTs) provide strong eventual consistency without coordination, but classical approaches assume benign participants. In Byzantine settings, convergence is typically enforced through agreement on update validity, often relying on identity-based filtering. However, such approaches struggle in post-compromise scenarios, where a previously correct participant becomes malicious: retroactive exclusion of its updates may break causal dependencies and invalidate subsequent computations. In this paper, we decouple identity-based trust from content-based trust and introduce a fine-grained trust model that combines both dimensions. Building on deterministic reconstruction, our approach allows replicas to preserve previously accepted updates while enabling selective inclusion or exclusion based on both the originating identity (e.g., public keys) and the semantics of individual updates. Trust decisions can incorporate application-level policies, enabling precise control over the impact of each update on the system state. Our approach preserves causal consistency and enables robust and flexible handling of both Byzantine and faulty behavior in decentralized CRDT systems.

0

quant-ph 2026-07-01

Unconditional bounds fix node count for quantum state certification

by Kenny Chen

Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification

Public-coin messages achieve exact tightness while private-coin quantum messages are nearly tight in the one-way distributed model.

abstract click to expand

Recently, Doosti et al. introduced the problem of distributed quantum state verification, where $m$ distributed nodes are given a copy of an unknown state $\rho$, and can send limited one way communication to a central node, who has a complete description of a known state $\sigma$. They ask how many distributed nodes $m$ are required, before the central node can succeed at distinguishing whether $\rho=\sigma$ or $\|\rho-\sigma\|_1\geq\varepsilon$ with high probability. In the setting where only quantum communication is allowed, Doosti et al. exhibit conditional lower bounds in both the public and private-coin settings, and a matching upper bound in the public-coin setting. We extend these results, and show unconditional lower bounds for when both classical and quantum communication are permitted. We show the public-coin lower bound is tight by giving an algorithm with a matching upper bound. We also show an almost tight upper bound in the private-coin setting when only quantum communication is permitted.

0

cs.DS 2026-07-01

Near-optimal Max E3LIN2 algorithms must flip Ω(n) outputs on one input change

by Yuichi Yoshida, Zihan Zhang

Sensitivity Lower Bounds via Locally Testable Codes

Reduction from locally testable codes shows satisfiable instances still force high sensitivity, matching trivial upper bounds and ruling out

abstract click to expand

Sensitivity quantifies how far an algorithm's output can move in Hamming distance when a single input element is perturbed. We present a general scheme turning any locally testable code (LTC) into a sensitivity lower bound for the CSP encoded by the code. Instantiating it with the $c^3$-LTC yields a constant $\varepsilon > 0$ for which every $(1-\varepsilon)$-approximation algorithm for satisfiable Max E3LIN2 has sensitivity $\Omega(n)$, strengthening the previous $\Omega(n^\delta)$ lower bound known only for general instances. Standard reductions give an $n^{1-O(\varepsilon)}$ lower bound for $n^{-\varepsilon}$-approximation algorithms for maximum clique, and an $\Omega(k)$ bound for $(1-\varepsilon)$-approximation algorithms for maximum $k$-coverage, among others. These lower bounds match trivial upper bounds and imply that even slightly stable algorithms cannot achieve these approximations. A second instantiation, using a simple repetition code, shows that any $(1-\varepsilon)$-approximation algorithm for Max Cut on bipartite graphs has sensitivity $\Omega(1/\varepsilon)$ as long as $\varepsilon = O(1/\sqrt{n})$, extending the prior result for exact algorithms (the regime $\varepsilon < 1/n$). Thus even on bipartite graphs, where a perfect cut always exists, near-optimal solutions cannot be maintained stably. Our sensitivity lower bounds have two applications. First, they yield averaged sensitivity lower bounds, implying that any nearly optimal randomized algorithm for Max E3SAT has linearly many output bits that, after fixing the random seed, are Boolean functions with large influence. Second, via the sensitivity-to-locality connection, they imply locality lower bounds in the non-signaling model, which generalizes $\mathsf{LOCAL}$ and quantum-$\mathsf{LOCAL}$.

0

cs.DS 2026-07-01

Spanning trees on generators orient networks in O(5.3334^ℓ n) time

by Jannik Schestag, Norbert Zeh

Orienting Unrooted Binary Networks Faster: Focus on the Generator

The orientation problem for multiple phylogenetic network classes reduces to enumerating directed spanning trees on the undirected generator

abstract click to expand

The problem of orienting an unrooted network to obtain a specific class of rooted phylogenetic networks is known to be NP-hard in many cases. In this paper, we introduce two algorithmic frameworks that yield significantly improved fixed-parameter tractable (FPT) algorithms parameterized by the network level $\ell$. Our first main contribution shows that for several prominent network classes, the core algorithmic difficulty lies in finding a directed spanning tree on the network's undirected generator. By enumerating these spanning trees in $O(5.3334^\ell + \ell)$ time and orienting all remaining edges in polynomial time, we solve the orientation problem in $O(5.3334^\ell \cdot n)$ time for tree-based networks and in $O(5.3334^\ell \cdot n^2)$ time for orchards, where $n$ is the number of vertices of the graph. Extending this approach with further branching yields $O(10.6667^\ell \cdot n^2)$-time algorithms for tree-child and normal networks. Our second technique bypasses spanning trees by directly guessing the placement of reticulations on the generator. This framework provides $O(12.2071^\ell \cdot n^2)$-time algorithms for temporal, reticulation-visible, and tree-sibling networks. Finally, we demonstrate the versatility of the reticulation-guessing framework by showing that even computing an orientation with minimum scanwidth is single-exponential FPT with respect to the level. Together, these results significantly improve the best-known running times for phylogenetic network orientation.

0

cs.DS 2026-07-01

Digraphs of pathwidth pw get O(pw)-diameter decompositions

by Shinwoo An, Arnold Filtser

Directed Low Diameter Decomposition for Structured Digraphs

The same analysis yields an O(tw log n) integrality gap for the directed sparsest-cut LP on treewidth-tw graphs.

abstract click to expand

Low diameter decompositions, or LDDs for short, are a fundamental primitive in the design of efficient graph algorithms. Roughly speaking, an LDD is a distribution over partitions of the vertices into bounded-diameter clusters such that nearby vertices are likely to be clustered together. Recently, there has been growing interest in lifting the notion of LDDs into \emph{directed graphs}. In particular, there are two natural directed analogues. The first is a directed LDD, where after removing a random subset of edges, every strongly connected component has a small diameter. The second is a quasipartition, which imposes the stronger requirement that whenever one vertex can still reach another after the edge removal, the two vertices must be close in the original directed metric. Every quasipartition yields an LDD, but the converse does not necessarily hold. In this work, we initiate the systematic study of LDDs in structured directed graphs. As our first main result, we show that any directed graph with pathwidth $\mathsf{pw}$ admits an $(O(\mathsf{pw}), \Delta)$-LDD. This improves upon the previous best-known $(2^{O(\mathsf{pw}^2)}, \Delta)$-LDD construction, which was implicitly derived from the quasipartition result of Salmasi, Sidiropoulos, and Sridhar [SODA'19]. As our second result, we show that the integrality gap of the Directed Non-Bipartite Sparsest-Cut LP relaxation on an $n$-vertex graph with treewidth $\mathsf{tw}$ is $O(\mathsf{tw} \log n)$. This improves upon the $O(\mathsf{tw}\log^2 n)$ bound of M\'emoli, Sidiropoulos, and Sridhar [ICALP'16, Algorithmica'18]. We obtain this result through the refined analysis of the quasipartition construction of M\'emoli et al. for bounded treewidth graphs.

0

cs.DS 2026-07-01

Iterated rounding extends to general graphs for (2+ε) bound

by Lars Rohwedder, Leander Schnaars

Graph Scheduling with Group Completion Times

Adapts bipartite coflow methods with matching polytopes and edge colorings, then improves data migration guarantees in every regime.

abstract click to expand

In the Graph Scheduling problem we schedule a given multiset of edges on discrete time steps, such that at each step the set of edges forms a matching. The goal is to minimize the sum of weighted group completion times, where a group is a set of edges and it completes when the last edge has been scheduled. Two popular variants of this problem are Coflow Scheduling and Data Migration. Our main result is extending a recent iterated rounding approach from Coflow Scheduling, roughly corresponding to the bipartite case, to the general Graph Scheduling problem. This yields an essentially tight $(2+\epsilon)$-approximation for the asymptotic setting where OPT is assumed to be large. For this we rely on polyhedral techniques from general matching, namely odd-set inequalities, and graph theoretical results on edge colorings in multigraphs. The state-of-the-art approximation algorithm for Data Migration is a $(1 + \phi)$-approximation that improves when OPT is small. Taking the best of this and our main result, we obtain an improvement of the approximation rate for Data Migration in any regime.

0

cs.DS 2026-07-01

Constant-factor approx for distance-2 sets in bounded merge-width graphs

by Maël Dumas

Constant-factor approximation of maximum distance-2 independent set in graphs of bounded merge-width

LP relaxation works when radius-2 merge-width is bounded, but the domination-to-independence ratio grows unbounded at radius-1.

abstract click to expand

We give a constant-factor approximation algorithm for Max Dist-2 Independent Set in graphs of bounded radius-2 merge-width. The same result holds for Min Dominating Set from [Bonamy and Geniet, 2025], [Chan et al., SODA '12]. Both approximation algorithms are LP-based, showing that the domination-to-2-independence ratio is bounded in graphs of bounded radius-2 merge-width. Moreover, this result is tight in the sense that the ratio can be unbounded in graphs of bounded radius-1 merge-width.

0

cs.DS 2026-07-01

Linear program gives first poly-time embedding of Okamura-Seymour quasimetrics

by Hung Le, Hector Tierno +1 more

Planar Embedding of Okamura-Seymour Quasimetrics in Polynomial Time with an Application to Distributed SSSP

The construction also yields Õ(D)-round (1+ε)-approximate SSSP in planar directed graphs under CONGEST, nearly matching the lower bound.

abstract click to expand

A quasi-metric $(T,\delta_T)$ is an Okamura-Seymour quasimetric if there exists an edge-weighted planar embedded directed graph $G = (V,E,w)$ such that $T$ is a set of terminals on the outerface of $G$ and $\delta_G(t,t') = \delta_T(t,t')$ for every pair $(t,t')\in T\times T$. If $(T,\delta_T)$ is an Okamura-Seymour quasimetric, then $G$ is a planar embedding of $(T,\delta_T)$. In a recent pioneering work, Chen and Tan gave a polynomial-time algorithm to test if a given quasi-metric $(T,\delta_T)$ is an Okamura-Seymour quasimetric. A key step in their proof is existential, which suffices for an efficient testing algorithm but does not imply an efficient embedding algorithm. Our paper closes this gap by giving an algorithmic implementation of their existential step via linear programming. As a result, we obtain the first polynomial-time algorithm for finding a planar embedding of any given Okamura-Seymour quasimetric $(T,\delta_T)$. As an application, we show how to use our planar embedding of Okamura-Seymour quasimetrics to compute a $(1+\epsilon)$-approximate single-source shortest path (SSSP) in planar directed graphs in the distributed CONGEST model in $\widetilde{O}(D)$ rounds for any fixed $\epsilon\in (0,1)$, nearly matching a simple lower bound of $\Omega(D)$ and resolving a fundamental problem in this area. The best-known algorithm for this problem has round complexity $\widetilde{O}(D^2)$.

0

cs.DS 2026-07-01

Linear-time algorithm builds smallest suffixient sets

by Francisco Olivares, Gonzalo Navarro

Practical Linear-Time Computation of Smallest Suffixient Sets

One-pass method from suffix arrays removes the main construction bottleneck for large repetitive collections.

abstract click to expand

Suffixient arrays are recent structures that have attracted attention because they offer relevant pattern matching functionality in less asymptotic space than the Run-Length BWT, the de-facto standard to index highly repetitive string collections. Various algorithms exist for building them from the suffix array data structures. We present the first construction algorithm that is (i) linear-time, (ii) one-pass over the structures, and (iii) implemented and practical. This makes the construction particularly useful on large text collections, which we demonstrate empirically by showing that it dominates the space/time tradeoff map of the implemented constructions.

0

cs.DS 2026-07-01

Optimal contextual matching now works in compressed space

by Gonzalo Navarro, Francisco Olivares

Optimal-Time Contextual Pattern Matching in Compressed Space

First O(m + occ) solution for distinct λ-contexts around pattern occurrences uses only a symmetric CDAWG plus a new ancestor structure.

abstract click to expand

Contextual pattern matching is the task of, given a pattern $P[1,m]$, a context length $\lambda$, and a text $T[1,n]$, find all the $occ$ distinct contexts in which $P$ occurs in $T$, the context being the $\lambda$ symbols preceding and the $\lambda$ symbols following the occurrence; a text position where each context occurs must be output. While the problem can be solved in optimal time $O(m+occ)$ using $O(n)$-space precomputed data structures on $T$, this type of search is particularly relevant on large repetitive text collections, where $O(n)$ space can be prohibitive. We present the first optimal-time solution that runs in compressed space, namely that of a symmetric CDAWG (SCDAWG) of $T$. Further, we show how the set of $occ$ solutions can be enumerated with $O(\log\log\lambda)$ delay after $O(m)$-time preprocessing of $P$. To achieve this, we develop an improved linear-space distance-sensitive weighted ancestor data structure.

0

cs.DS 2026-06-30

Geodetic set is FPT on chordal graphs

by Dibyayan Chakraborty, Sandip Das +3 more

Algorithms and complexity for geodetic sets on interval and chordal graphs

The problem admits f(tree-width) * n^O(1) algorithms on chordal graphs and is NP-hard even when restricted to interval graphs.

abstract click to expand

We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set $S$ of vertices of a graph $G$ is a \textit{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. We show that \textsc{Minimum Geodetic Set} is fixed parameter tractable for chordal graphs when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$-trees, for fixed $k$. Then, we show that \textsc{Minimum Geodetic Set} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012), who showed that \textsc{Minimum Geodetic Set} is polynomial-time solvable on proper interval graphs. As interval graphs are very constrained, to prove the latter result, we design a rather sophisticated reduction technique to work around their inherent linear structure.

0

math.OC 2026-06-30

Library solves SPPRC 1.3-2.35 times faster than PathWyse

by Simon Spoorendonk

texttt{bucket-graph-spprc}: an extensible C++ library for the shortest path problem with resource constraints

bgspprc uses compile-time resources and bucket-graph labelling for faster pricing in vehicle routing solvers.

abstract click to expand

We present $\texttt{bucket-graph-spprc}$ ($\texttt{bgspprc}$ for short), an open-source, header-only C++23 library for the shortest path problem with resource constraints (SPPRC), the pricing subproblem at the heart of branch-cut-and-price for vehicle routing and related problems. The library implements the bucket-graph labelling algorithm of Sadykov, Uchoa and Pessoa (2021), with bidirectional labelling, across-arc concatenation, bucket fixing and arc elimination, and a structure-of-arrays label store with SIMD-accelerated dominance. Its central design feature is a compile-time resource concept: a new SPPRC variant is added by implementing a fixed seven-function interface, and resources compose into a label state with no runtime dispatch, the state layout fixed at compile time. Five resources ship built in: time/capacity, ng-path elementarity relaxation, rank-1 cuts, cumulative cost, and pickup-and-delivery. In a reproducible, head-to-head comparison on shared public instances at an identical bound, $\texttt{bgspprc}$ outperforms PathWyse (Salani, Basso and Giuffrida, 2024), the main open-source comparator, by $1.3\times$--$2.35\times$ in shifted geometric mean (and by $1.3\times$--$2.3\times$ even when itself run single-threaded), and runs within $1.9\times$--$2.4\times$ of parallel pull labelling (Petersen and Spoorendonk, 2025), a different labelling technique for the same problem. The library, benchmark scripts, and pinned instances are publicly available.

0

quant-ph 2026-06-30

Simpler qudit flow definition yields O(n^3) algorithm

by Piotr Mitosek, Miriam Backens

Working with measurement-based computations on qudits

Updated conditions on prime-dimensional graph states match qubit complexity and support optimization transformations.

abstract click to expand

Measurement-based quantum computing is a universal model of quantum computation in which successive product measurements of an entangled resource state drive the computation. The non-deterministic nature of measurements necessitates adaptivity to ensure an overall deterministic computation. Flow structures characterise cases in which such an adaptive correction procedure is possible. Recently, flow has been defined in a setting where the resource states are prime-dimensional qudit graph states rather than the usual qubit graph states. Yet, this qudit flow definition is more burdensome to work with than analogous definitions for qubits. Here, we give a simpler definition of qudit flow and consider various useful properties of this flow, drawing on results for the qubit case. In particular, we show how to focus qudit flow and argue that focused flow is canonical. We improve the previous algebraic formulation to capture focused flow and use it to obtain an $O(n^3)$ flow-finding algorithm (where $n$ is the number of qudits), matching the best known complexity for qubit flows and improving on the previous $O(n^4)$ result for qudits. Furthermore, we explore multiple flow-preserving transformations, thus opening a pathway to using flow for optimisation. These transformations include pivoting, removal and insertion of certain types of vertices, and reversibility of flow. Lastly, we propose an algorithmic approach to generating large qudit computations with flow, for testing or machine learning.

0

cs.DS 2026-06-30

Bounded k-submodular functions admit constant-query testers in ℓ_p

by Themistoklis Haris, Diptaksho Palit

Testing k-submodularity

Junta closeness on hypergrids enables this result, while Hamming distance reveals opposing repair directions for the two violation types.

abstract click to expand

We initiate the study of property testing for $k$-submodular functions, a higher-dimensional analogue of submodular functions defined on partial partitions of a ground set. While $k$-submodularity retains the diminishing-returns flavor of ordinary submodularity, it also introduces a pairwise monotonicity constraint comparing competing assignments of the same element. This additional local structure makes the testing problem qualitatively different from the classical case. Our results show a sharp contrast between distance regimes. In the $\ell_p$ regime for $p \geq 1$, we prove that every bounded $k$-submodular function is close to a junta on the hypergrid. Combined with an implicit-learning tester for hypergrid domains, this yields a constant-query tester for $k$-submodularity. In the Hamming distance regime, $k$-submodularity admits two qualitatively different local witnesses -- violated squares for diminishing marginal gains, and violated triangles for pairwise-monotonicity failures -- and the latter has no counterpart at $k=1$. We prove density theorems for both witness types via repair on filters and ideals of partial partitions, yielding non-adaptive, one-sided sub-exponential-query testers for the two component properties of $k$-submodularity. We then exhibit a configuration in which the two repair directions are forced into opposition on a shared vertex, identifying a structural barrier to combining these into a tester for the full property. Finally, for bounded-range functions, we give an adaptive tester for monotone $k$-submodularity via a pseudo-DNF representation and learning on the hypergrid. Several of the structural and learning tools developed here may be useful for testing other properties over product domains.

0

quant-ph 2026-06-30

Algorithm learns Lindbladian coefficients with O(d² log n / ε²) evolution time

by Laura Lewis, Ewin Tang +1 more

Learning the structure of open quantum systems

Works from non-adaptive Pauli measurements without knowing the interaction graph and extends to Hamiltonians from Gibbs states.

abstract click to expand

We design an algorithm for learning the coefficients of an $n$-qubit constant-local Lindbladian to $\varepsilon$ error with $O(g d^2 \log(n) / \varepsilon^2)$ total evolution time, where $g$ is the single-site energy and $d$ is the (approximate) degree of the interaction graph. Though Lindbladians present new challenges not present in the special case of Hamiltonians, our algorithm achieves the suite of desiderata attained by state-of-the-art Hamiltonian learning algorithms: (1) it uses non-adaptive, ancilla-free randomized Pauli measurement circuits with a time resolution of only $\Theta(1/g)$; (2) it works without knowledge of the structure of the unknown Lindbladian; (3) it depends on a smooth form of degree, thereby supporting the learning of quasi-local and power-law Lindbladians. Our algorithm is a simple iterative method, where the objective function consists of Fourier coefficients of the Lindbladian restricted to few-site regions. Its analysis identifies the difficulty unique to open systems, which we call "confusing" terms. For settings where the "confusion" is limited, the performance of the algorithm improves. We demonstrate this for the case of structure learning of Hamiltonians from access to real-time evolution, where we obtain a new algorithm that is significantly simpler than previous work. In addition, using the same iterative method, we design the first efficient algorithm for structure learning Hamiltonians from high-temperature Gibbs states.

0

cs.DS 2026-06-30

Uniform sample of size O(1/ε² log 1/ε) is stable coreset for geometric median

by Amir Carmel, Robert Krauthgamer +1 more

Optimal Stable Coresets for Geometric Median via Uniform Sampling

Size is independent of dimension and tight up to logs, enabling sublinear preprocessing for constrained variants.

abstract click to expand

The geometric median problem asks to find a point in $\mathbb{R}^d$ that minimizes the sum of Euclidean distances to an input set. It is a classical problem in computational geometry and appears as a subroutine in numerous optimization tasks, many of which require the solution to satisfy additional structural constraints. A common approach to reduce the input size is to construct a coreset, which is a small weighted subset that faithfully represents the input for a specific optimization problem. Strong coresets preserve the cost of every candidate solution but require linear time to construct; weak coresets admit sublinear construction, in fact by uniform sampling, but only preserve near-optimal solutions, which is insufficient when the solution is constrained. To address this, we focus instead on the recently introduced intermediate notion of a \emph{stable coreset}, which simultaneously handles all constrained variants. Currently, there is a large gap between the known sample sizes for stable and weak coresets. Our main result is that a uniform sample of size $O(\epsilon^{-2} \log \tfrac{1}{\epsilon})$ is a stable $(\epsilon, O(\epsilon))$-coreset for the geometric median, with high constant probability, and this bound is tight up to the logarithmic factor. Our analysis adapts recent machinery of Carmel and Krauthgamer (ICLR 2026) for constructing stable coresets, which incurs an $O(\log d)$ factor. We show an iterative argument that progressively reduces the sample size, and eliminates this dependence on the dimension $d$. At a high level, this approach resembles the technique of iterative size reduction, which is applicable for strong coresets but not for weak coresets.

0

cs.GT 2026-06-30

Discounted i.i.d

by Jung-Hun Kim, Vianney Perchet

I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case

Even structured multiplicative discounting over phases erases the usual i.i.d. advantage and matches non-i.i.d. hardness.

abstract click to expand

We study prophet inequalities with discounted rewards, where i.i.d. base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitrarily weak form of nonstationarity can erase the classical advantage of the stationary i.i.d. setting. Focusing on single-quantile threshold policies, we show that the competitive ratio transitions from the classical $1-1/e$ guarantee to a fundamental $1/2$ barrier as discounting accumulates over many phases in a canonical regime with a common-decay factor and equal-length phases. We further show that, in the same regime, the $1/2$ barrier persists even for arbitrary stopping rules. Consequently, i.i.d. base rewards under discounting can be as hard as the fully non-i.i.d. case. On the algorithmic side, we design single-quantile threshold rules that attain the tight bounds by calibrating acceptance decisions to an effective horizon induced by discounting, and we extend this calibration to heterogeneous decay factors and unequal phase lengths. We further show that a similar discontinuous breakdown persists in an infinite-horizon continuous-decay benchmark, where arbitrarily weak decay collapses the stationary benchmark from $1$ to $1/2$.

0

cs.CR 2026-06-30

Exact privacy math for 2020 Census now 1824 times faster

by Buxin Su, Weijie Su +1 more

A Sieve-Accelerated Quadrature Method for Exact Privacy Accounting in the 2020 U.S. Decennial Census

Sieve-accelerated quadrature evaluates high-dimensional noise convolutions to 10^{-35} precision without assumptions, allowing minimal noise

abstract click to expand

In 2020, the U.S. Census Bureau adopted differential privacy for the Decennial Census by injecting integer-valued Gaussian noise into published census tabulations. Exactly evaluating the privacy guarantees of these data releases would enable the Bureau to determine the absolute minimum noise required to satisfy a given privacy budget, preventing the injection of unnecessary excess noise and thereby substantially enhancing the statistical utility of the data for downstream applications such as federal funding allocation and political redistricting. In this paper, we introduce a computationally efficient and mathematically rigorous quadrature method to evaluate the exact privacy profile of practical, large-scale census releases under the composition of heterogeneous discrete Gaussian mechanisms. Mathematically, this problem reduces to evaluating the tail probabilities of high-dimensional convolutions of integer-valued random variables sampled from heterogeneous discrete Gaussian distributions under exceptionally stringent numerical error tolerances (e.g., $10^{-35}$). By recasting the exact privacy accounting as a numerical integration problem via the discrete Fourier transform, we explicitly exploit the exponential convergence of the trapezoidal rule for complex analytic, periodic characteristic functions. Furthermore, to overcome the computational bottleneck of evaluating highly oscillatory integrands in high dimensions, we develop a sieve algorithm that identifies and prunes negligible quadrature nodes, accelerating the computation by three orders of magnitude. Taken together, these numerical innovations enable the first exact, assumption-free privacy accounting for the 2020 Census Demographic and Housing Characteristics File, achieving a 1,824-fold speedup over prior methods while maintaining census-mandated error tolerances.

0

cs.DS 2026-06-29

FPT algorithm decides cycle rank <=w on semi-complete digraphs

by Seokbeom Kim, O-joung Kwon +1 more

An FPT algorithm for cycle rank on semi-complete digraphs

Runs in O(9^{(w+1)4^{w+2}} n²) time after reduction to bounded directed clique-width.

abstract click to expand

Cycle rank is a depth parameter for digraphs introduced by Eggan in 1963. Gruber (DMTCS 2012) and Giannopoulou, Hunter, and Thilikos (DAM 2012) asked whether the problem of determining if a given digraph has cycle rank at most $w$ is fixed-parameter tractable parameterized by $w$. We provide such algorithms for semi-complete digraphs, and for digraphs of bounded directed clique-width. Specifically, we show that given an $n$-vertex semi-complete digraph $G$ and an integer $w$, one can in time $\mathcal{O}(9^{(w+1)4^{w+2}} \cdot n^2)$ determine whether $G$ has cycle rank at most $w$. The proof is reduced to the case of bounded directed clique-width, and we then show that given an $n$-vertex digraph $G$ with a directed clique-width $k$-expression and an integer $w$, one can in time $\mathcal{O}(9^{(w+1) 4^k} \cdot n)$ determine whether $G$ has cycle rank at most $w$. Additionally, we consider the \textsc{Minimum Feedback Arc Set} problem on semi-complete digraphs, and show that it can be solved in time $n^{\mathcal{O}(w)}$, where $w$ is the cycle rank of the given semi-complete digraph.

0

cs.DS 2026-06-29

Lewis weights computed in O(p² log(m/ε)) leverage rounds

by Sander Gribling, Aaron Sidford +1 more

Computing Lewis weights to high precision using local relative smoothness

Local relative smoothness on primal and dual problems improves prior O(p³) round bound for p ≥ 4.

abstract click to expand

We provide algorithms that compute $\epsilon$-estimates of the $\ell_p$-Lewis weights of a matrix $A \in \mathbb{R}^{m \times n}$ for $p \geq 4$ using $O(p^2 \log(m/\epsilon))$ rounds of leverage score computation, where $\ell_p$-Lewis weights and leverage scores are both standard measures of row importance. This improves upon the state-of-the-art round complexity of $O(p^3 \log(m/\epsilon))$ due to Fazel, Lee, Padmanabha, and Sidford (2022). We obtain our results by carefully applying a local variant of relatively smooth gradient descent to primal and dual forms of the $\ell_p$-Lewis weight optimization problem and providing tools to convert between different notions of approximate $\ell_p$-Lewis weights.

0

cs.DS 2026-06-29

Protocol gossips in Õ((mn)^{3/5}) time on sparse radio graphs

by Chao Wu, Marek Chrobak

A Gossiping Protocol for Sparse Ad-Hoc Radio Networks

Improves Õ(n^{4/3}) bound for m-edge networks and gives Õ(√Δ n) for regular graphs.

abstract click to expand

We study the problem of gossiping (all-to-all information exchange) in ad-hoc radio networks. Such a network is represented by a strongly-connected directed graph with $n$ vertices, whose topology is initially unknown to the protocol. In 2004, Gasieniec, Radzik, and Xin gave a $\tilde O(n^{4/3})$-time deterministic protocol for this problem, and closing the gap between their upper bound and the $\tilde\Omega(n)$ lower bound on the time complexity of gossiping remains a central open problem. We develop a deterministic protocol for gossiping in ad-hoc radio networks that achieves running time $\tilde O((mn)^{3/5})$ for directed graphs with at most $m$ edges. Our protocol improves on the $\tilde O(n^{4/3})$ bound when $m = O(n^c)$, for $c < 11/9$. We also present a $\tilde O(\Delta^{1/2} n)$-time gossiping protocol for $\Delta$-regular graphs.

0

cs.DC 2026-06-29

Depth thresholds adapt concurrent trees to skewed access

by Vitaly Aksenov, Rene van Bevern +1 more

Concurrent Splay-Based Tree

Limited rotations based on access counts raise throughput on Zipfian workloads while cutting root contention.

abstract click to expand

Most work on efficient concurrent ordered indices, such as concurrent binary search trees, B-trees, skip lists, etc., has focused on data structures that provide good \emph{worst-case} guarantees. In real workloads, objects are often accessed at different rates, since access distributions may be non-uniform. Many efficient distribution-adaptive data structures exist in the sequential case; however, they are often complicated to make efficient in the concurrent case. The most prominent distribution-adaptive data structure is Splay Tree. Its most important advantage is that it does not store any balancing information and provides a reasonable performance improvement on extremely skewed workloads, such as Zipfian workloads. This paper proposes a splay-like rotation design for concurrent binary search trees. Instead of moving an accessed node to the root, rotations use two depth thresholds that are based on the static-optimality complexity computed from the number of accesses to the node: a node is rotated only when it is substantially deeper than the upper threshold, and rotations of the node stop before reaching the lower threshold. This design aims to preserve the main practical benefit of splaying on skewed workloads while reducing contention near the root. We present two variants of the rotation design: one using an exact 64-bit access counter per node and one using a 6-bit approximate counter. We prove static optimality for the corresponding sequential read-only tree and evaluate both rotation designs by implementing them on top of the concurrent AVL tree of Bronson et al. Our experiments show that the approach can improve throughput on several skewed workloads.

0

cs.DS 2026-06-29

Adaptive scaling improves incremental submodular maximization to 1.373

by Marcin Bienkowski, Joakim Blikstad +4 more

Incremental Submodular Maximization: Better Than Greedy

The algorithm beats greedy's 1.582 ratio across all cardinalities and comes with a 1.25 deterministic lower bound.

abstract click to expand

We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of the ordering yields a good solution for its respective cardinality. A classical result in this setting is that the greedy algorithm achieves a competitive ratio, i.e., an approximation guarantee across all cardinalities, of $\mathrm{e}/(\mathrm{e}-1) \approx 1.582$. No better general guarantee was previously known. We present an adaptive scaling algorithm achieving a competitive ratio of $1.373$. We complement our result by a deterministic lower bound of $1.25$ on the best possible competitive ratio for incremental submodular maximization.

0

cs.LG 2026-06-29

Reward-tilted remasking scales masked diffusion quadratically

by Kijung Jeon, Thuy-Duong Vuong +1 more

VGB for Masked Diffusion Model: Efficient Test-time Scaling for Reward Satisfaction and Sample Editing

MDM-VGB extends backtracking walks to masked graphs for efficient reward satisfaction and editing while avoiding exponential error buildup.

abstract click to expand

Inference-time scaling is a promising paradigm to improve generative models, especially when outputs must satisfy structural constraints or optimize downstream rewards. We consider Masked Diffusion Model (MDM) and introduce MDM-VGB, a discrete diffusion sampler that augments unmasking generation with theoretically principled reward-guided remasking. Inspired by the recent success of the classical Jerrum-Sinclair backtracking Markov chain in reward-tilted generation, MDM-VGB extends the backtracking random walk from a fixed prefix tree to a masked-state graph, allowing tokens to be unmasked and remasked at arbitrary positions. The resulting sampler favors unmasking and remasking moves that lead to higher-value partial configurations, enabling both effective high-reward generation and efficient repair of low-reward samples. We prove that MDM-VGB is robust to process-verifier noise and achieves quadratic complexity, while popular test-time heuristics such as best-of-$N$ can incur exponential complexity due to error accumulation. Our theoretical findings are corroborated by strong empirical performance, particularly on popular constraint-satisfaction and scientific benchmarks such as Sudoku and QM9.

0

cs.DS 2026-06-29

Planar max-cut algorithm gives upper bounds for toroidal graphs

by Mark Glass, Meir Feder

Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs

The reduction adapts a 1975 algorithm to negative weights and shows some GSet toroidal solutions are optimal.

abstract click to expand

We demonstrate that the problem of finding the maximum cut of a planar graph with arbitrary weights can be easily mapped to a minimum T-join problem in the absolute dual graph - the dual graph with absolute weights, as opposed to the known mapping to a maximum T-join problem with an empty set in the dual graph. By enabling the use of the shortest paths, this approach allows for the straightforward adaptation of the first efficient Max-Cut algorithm, designed by Hadlock in 1975 for planar graphs with non-negative weights, to handle the general case of planar graphs with arbitrary weights. Furthermore, we prove that applying a planar Max-Cut algorithm to a higher genus graph, such as a toroidal graph, while disregarding its topology, provides an upper bound for its maximum cut. Employing this methodology, we derive upper bounds for the maximum cut across all toroidal graphs within the GSet benchmark. We report that the known maximum cut values for part of those GSet toroidal problems including the three largest instances, which were previously documented in the literature, are the maximum possible because they match their upper bound values. Additionally, we introduce a novel heuristic algorithm for finding Max-Cut of toroidal graphs, which is based on the planar graph algorithm. Applying this algorithm to all seventeen toroidal Max-Cut problems in the GSet benchmark successfully reproduces all the best-known results, and for problem #62, it yields a new, previously unknown best Max-Cut value.

0

cs.DS 2026-06-29

Exponential walks required to approximate spectra of unweighted graphs

by Pan Peng, Yuyang Wang +2 more

An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs

No algorithm succeeds with constant probability using 2^Ω(1/ε^{1/6}) transcripts of length 2^Ω(1/ε^{1/6}) from random nodes.

abstract click to expand

We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\varepsilon)}$ random walks initiated from uniformly random nodes in the graph. Later, Jin et al. [COLT 2023] established a nearly matching exponential lower bound for \emph{weighted} graphs, assuming the algorithm has access to samples from random walks started at random nodes. It was left open whether this lower bound could be extended to \emph{unweighted} graphs. In this paper, we answer this question in the affirmative by proving an exponential lower bound for unweighted graphs. Specifically, we show that no algorithm can compute an $\varepsilon$-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of $2^{\Omega(1/\varepsilon^{1/6})}$ random walks, each of length $2^{\Omega(1/\varepsilon^{1/6})}$, started from uniformly random nodes.

0

cs.DS 2026-06-29

Shattering arguments need new decay bounds after independence fails

by Mohsen Ghaffari, Magnús M. Halldórsson +2 more

Robust Shattering Arguments

Pre-shattering phases lasting many rounds accumulate dependencies, so prior proofs for LLL, MIS, and coloring are repaired without those ass

abstract click to expand

Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that large sets of distant nodes remain unresolved, often via independence assumptions justified by locality. We show that these assumptions fail for pre-shattering procedures that run for super-constant rounds, where dependencies accumulate over time. As a result, several standard shattering arguments in the literature are incomplete, including those for maximal independent set, $(\Delta+1)$-coloring, and the distributed Lov\'asz Local Lemma (LLL). We provide a systematic repair of these analyses. Our main contribution is a corrected shattering analysis of the Fischer--Ghaffari LLL algorithm. In addition, we develop general tools that capture common patterns in modern algorithms and yield the required decay bounds without relying on independence. We also present explicit counterexamples to commonly used shattering lemmas. Overall, we establish a robust and reusable foundation for shattering arguments in the presence of long-range dependencies.

0

cs.DS 2026-06-29

Sparse triangle problems now beat their trivial time bounds

by Neha Pant, Ryan Williams

Beating Trivial Time for Tricky Triangle Tasks

First Word-RAM speedups for All-Edges Sparse Triangle, Monochromatic Triangle, and Exact Triangle via circuit and communication techniques.

abstract click to expand

For several well-studied triangle detection problems in the literature, the trivial enumeration algorithms are known to be optimal (up to the exponent) assuming popular fine-grained conjectures. For example, All-Edges Sparse Triangle and Sparse Monochromatic Triangle where each node has degree $n^{\delta}$ for some $\delta < 1$, and the Exact Triangle where edges have arbitrary weights, all have this property under the 3SUM Conjecture. However, as there are slightly nontrivial algorithms for 3SUM, it is natural to wonder if the trivial algorithm for these tricky triangle tasks might also be improved. Applying a variety of techniques from randomized algorithms, circuit complexity, and communication complexity, we present the first improvements over the trivial algorithms for each of these problems in the Word RAM model. Moreover, our algorithms can be implemented with only polysize $AC0$ operations on words. Extending our techniques, we also show how to solve the notorious 4-cycle detection problem on $n$-node graphs in $o(n^2)$ time, in a Word-RAM model with word size $w > \omega(\log^2 n)$. Along the way, we show how to sort $n$ items over a universe of size $2^u$ using only $AC0$ word operations in $O(n u \log n)/w$ time.

0

math.PR 2026-06-26

Short proof establishes rapid mixing past uniqueness on random graphs

by Andreas Göbel, Matthew Jenssen +4 more

A simple proof of rapid mixing on random regular graphs beyond uniqueness

Bochner-Bakry-Émery expansion cancels the sum-of-squares term to give the Poincaré inequality directly for Glauber dynamics.

abstract click to expand

A recent breakthrough of Chen, Chen, Chen, Yin, and Zhang shows rapid mixing for Glauber dynamics for the hard-core model on random regular graphs beyond the tree uniqueness threshold. Their approach builds upon the literature of various local-to-global techniques and applies to a more general setting of discrete distributions supported on downward-closed set families. We give a short and self-contained proof via a Bochner--Bakry--\'{E}mery approach and directly show a Poincar\'e inequality by expanding the Dirichlet form in terms of the $L^2$-norm of the generator applied to a test function and eliminating a sum of squares term. Our proof is a streamlined version of an argument of Kondratiev, Kuna, and Ohlerich used to study spatial birth-and-death dynamics for Gibbs point processes in the continuum, which we adapt to the discrete setting.

0

cs.DS 2026-06-26

O(Δ) deterministic algorithm for incremental dominating set

by Ilan Doron Arad, Jonathan Gal +1 more

Incremental Dominating Set

The incremental benchmark constrains the optimum to online choices, enabling O(Δ) deterministic and O(log²Δ) randomized ratios that are tigh

abstract click to expand

Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected vertex. In online settings where vertices arrive sequentially, comparing algorithms against an offline optimum with full knowledge of the input leads to extremely strong lower bounds, where even a simple star graph shows that any online algorithm must have competitive ratio $\Omega(\Delta)$, with $\Delta$ the largest degree of any vertex in the graph, matching the trivial strategy of selecting all vertices. We study the incremental dominating set problem, where the optimal algorithm is constrained to the same choices available to online algorithms. This introduces a benchmark that enables a meaningful comparison between algorithms. We present the first results for vertex-weighted graphs and randomized algorithms in this model. For incremental dominating set, we give an $O(\Delta)$-competitive deterministic algorithm and an $O(\log^2\Delta)$-competitive randomized algorithm. We extend these results to the Connected Dominating Set problem using a linear-programming formulation that captures connectivity through local constraints. When the neighborhood of each arriving vertex is known \textit{in advance}, deterministic algorithms achieve similar polylogarithmic competitive ratios as their randomized counterparts. Finally, we establish matching lower bounds, showing that our results are optimal up to constant factors.

0

cs.DS 2026-06-26

Halfspace truncation adds no sample cost to Gaussian learning

by Haitong Liu, Deepak Narayanan Sridharan +2 more

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

Õ(d²/ε²) samples suffice via moment reinterpretation through a relative truncation parameter that directly recovers the original mean and co

abstract click to expand

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

0

cs.DM 2026-06-26

Pinwheel schedules exist for all densities up to 5/6

by Akitoshi Kawamura

Proof of the Density Threshold Conjecture for Pinwheel Scheduling

Fractional-period reduction collapses the 1993 conjecture to a finite computer check.

abstract click to expand

In the pinwheel scheduling problem, each task $i$ is associated with a positive integer $a_i$ called its period, and we want to (perpetually) schedule one task per day so that each task $i$ is performed at least once every $a_i$ days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates $1/a_i$, does not exceed $1$. We prove that all instances with density not exceeding $5/6$ are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress towards the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (non-integer) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most $1$ is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio $4/3$.

0

cs.LG 2026-06-26

Comparisons reach ε-stationary points in Õ(n²/ε^{1.5}) queries

by Helin Wang, Chenyi Zhang +3 more

Finding Stationary Points by Comparisons

Classical and quantum algorithms locate points of small gradient norm using only pairwise function-value comparisons for twice-differentiabl

abstract click to expand

We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that visits an $\epsilon$-stationary point using $\widetilde O(n^2/\epsilon^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $\delta$ using $\widetilde O(n^2\log(1/\delta))$ queries. We further study this problem with a quantum comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an $\epsilon$-stationary point, which takes $\widetilde O(n/\epsilon^{1.5})$ queries.

0