Data Structures and Algorithms
See recent articles
Showing new listings for Thursday, 19 November 2026
- [1] arXiv:2611.23540 [pdf, html, other]
-
Title: Size-Independent Survival Bounds for Routing Without a MapComments: 38 pages, 11 figures. Follow-up to arXiv:2609.00893Subjects: Data Structures and Algorithms (cs.DS)
A walker, such as a packet carrying a secret share, must reach a known target in an unknown graph while avoiding a fixed set of fatal vertices (compromised relays in the packet interpretation). It learns a vertex's neighbours only on reaching that vertex safely, remembers its observations, and is promised a safe route. We prove that a randomised depth-first strategy guarantees a success probability depending only on the maximum degree and the number of fatal vertices, not on the size of the graph. Planarity is not required for this guarantee, and planar examples attain the bound at every sufficiently large graph size. At those sizes, when the degree cap is at least three, the guarantee is optimal among strict depth-first strategies. Whether strategies allowed to switch between unfinished branches can guarantee a larger worst-case survival probability remains open. For unknown trees and for graphs of maximum degree two, we determine the exact best worst-case success probability over all routing strategies. Explicit examples compare our strategy with random-priority frontier routing and ordinary random walks, showing how exploration order can prevent survival probability from declining as the graph grows.
- [2] arXiv:2611.23637 [pdf, html, other]
-
Title: Optimal universal sets for submodular functionsComments: Results obtained with the assistance of GPT-6 AstraSubjects: Data Structures and Algorithms (cs.DS)
We resolve the question of deterministic non-adaptive algorithms for nonnegative submodular maximization: We prove that for every $n \geq 2$ and $\epsilon \in (0,\frac{1}{4})$, there is a polynomial-size family ${F}_{n,\epsilon}$, $|{F}_{n,\epsilon}| = n^{O(1/\epsilon^2 \log (1/\epsilon))}$, such that for every nonnegative submodular function $f:2^{[n]} \to {\bf R}$, $\max_{S \in {F}_{n,\epsilon}} f(S) \geq (1/4 - \epsilon) \max_{S \subseteq [n]} f(S)$. It is also easy to show that a factor better than $1/4$ cannot be achieved by any fixed polynomial-size family.
A related result that we prove is that there is a distribution ${D}_{n,\epsilon}$ supported on polynomially many subsets of $[n]$ such that $(1 - \epsilon) {\bf E}_{R \sim {U}_n}[f(R)] \leq {\bf E}_{R \sim {D}_{n,\epsilon}}[f(R)] \leq {\bf E}_{R \sim {U}_n}[f(R)]$, where ${U}_n$ is the uniform distribution on $2^{[n]}$, and $f$ is any nonnegative submodular function. This is interesting in light of the fact that uniform convergence does not hold for submodular functions: Sampling polynomially many sets from ${U}_n$ and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions.
The construction of ${F}_{n,\epsilon}$ and ${D}_{n,\epsilon}$ is based on a new semidefinite extension of submodular functions: We show that the Goemans-Williamson rounding technique for a near-orthogonal arrangement of vectors gives a value close to the uniform expectation, and this rounding can be derandomized, since near-orthogonal vectors can be constructed in logarithmic dimension. - [3] arXiv:2611.23653 [pdf, html, other]
-
Title: Faster polynomial-space algorithms for poset problemsSubjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
We give a polynomial-space, deterministic, exact algorithm for counting linear extensions of partial orders over $n$ elements, with running time $O^*((2\sqrt{2})^{n}) \subseteq O(2.829^n)$. This improves upon the long-standing bound of $O^*(4^{n})$ attainable by standard divide and conquer (Savitch 1970, Gurevich and Shelah 1987). Our algorithm uses a similar balanced splitting approach as the classical algorithm, but applies it only to the elements outside a largest antichain. For the elements of the antichain itself we develop a formula based on inclusion-exclusion that accounts for the ways in which they can appear in a linear extension. The technique is also applicable to other problems on posets, which we illustrate by solving the well-studied jump number problem in a similar running time of $O^*((2\sqrt{2})^{n})$ and polynomial space. To our knowledge, these are the first polynomial-space algorithms with a running time below $4^n$ for both problems.
- [4] arXiv:2611.24201 [pdf, html, other]
-
Title: A (12/11+eps)-Approximation for Nonpreemptive Throughput MaximizationMikhail Cherniavskii, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev, Fedor Ozhegov, Alexander ShekhovtsovSubjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
We study unweighted nonpreemptive throughput maximization on an arbitrary number of identical machines: each job has a processing time and a release--deadline window, and the goal is to schedule as many jobs as possible. For every fixed $\varepsilon>0$, we give a randomized $(12/11+\varepsilon)$-approximation. This improves the recent $(4/3+\varepsilon)$-approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the $(17/13+\varepsilon)$-approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time $n^{O_\varepsilon(1)}\operatorname{poly}(N)$, where $N$ is the input length.
- [5] arXiv:2611.24211 [pdf, html, other]
-
Title: Expand & Reduce: a Framework Bridging Branch-and-Reduce and Dynamic ProgrammingComments: 18 pages, 5 figures. Code and data links included in paperSubjects: Data Structures and Algorithms (cs.DS)
We introduce expand-and-reduce, a framework that augments classical reduction rules with a new type of optimality-preserving operation, called an expansion rule. While a reduction rule in practice typically makes the instance smaller, an expansion rule may enlarge the instance yet still making progress towards a solution. We present a simple expansion rule called edge expansion for the Maximum Weighted Independent Set (MWIS) problem. It encodes the joint choice of two non-adjacent vertices by adding an edge between them and creating a new vertex representing their union. We prove that the number of edge expansions needed to transform a graph into a clique equals the number of independent sets in the graph minus the number of vertices. We demonstrate that expand-and-reduce, using edge expansion and just two well-known reduction rules, has greater reduction power than a set of 22 commonly used reduction rules for MWIS. Therefore, it can significantly simplify methods that depend on reduction rules. To highlight the practical potential of the expand-and-reduce framework further, we provide an implementation and preliminary results showing that a simple implementation outperforms a far more advanced method for MWIS preprocessing. Moreover, expand-and-reduce can simulate both branching and dynamic-programming-style state construction, yielding exact and fixed-parameter algorithms with matching asymptotic running times. By that, expand-and-reduce offers a unified and conceptually clean perspective on techniques that are usually considered incompatible.
- [6] arXiv:2611.24239 [pdf, html, other]
-
Title: Approximation Algorithms for Product Query OptimizationMacéo Ottavy, Avijeet Ghosh, Pascal Koiran, Alantha Newman, François Schwarzentruber, Blair D. Sullivan, Stéphan ThomasséSubjects: Data Structures and Algorithms (cs.DS)
We study database query optimization for Cartesian products. This problem is equivalent to finding an optimal plan for multiplying non-negative integers. We call this problem multiplication ordering. We show that the problem has an FPTAS when the cost of a plan is the sum of all intermediate products; both in the case when the overall final product is counted and when it is not. We show that using the optimal solution to the well-known product partition problem does not always lead to an optimal plan, but we establish connections between the product partition and multiplication ordering problems. Finally, we prove that multiplication ordering is in PTIME (resp. \NP-complete) when integers are powers of a same base where the exponents are written in unary (resp. in binary).
- [7] arXiv:2611.24385 [pdf, html, other]
-
Title: Improved Bounds for Online TSP on the Half-LineSubjects: Data Structures and Algorithms (cs.DS)
In the open online traveling salesperson problem, requests appear over time at different positions of a metric space. A single agent traveling at unit speed must serve all requests, by visiting their positions, with the objective of minimizing the completion time. We propose online algorithms for this problem for the case that the metric space is the half-line. First, we present a $2$-competitive algorithm in which the server always either moves at unit speed or remains stationary, which improves on the previously best-known ratio of $2.04$. We further observe that algorithms must sometimes move slower than unit speed to achieve competitive ratios below $2$. We introduce a second algorithm that beats the barrier of $2$ by carefully modulating its speed, and prove a tight bound of $1.75$ on its competitive ratio. Finally, we slightly strengthen a known lower bound on the best-possible competitive ratio on the half-line from $1.627$ to $1.646$.
- [8] arXiv:2611.24386 [pdf, html, other]
-
Title: Even Faster Algorithms for Bounded Integer ProgrammingSubjects: Data Structures and Algorithms (cs.DS)
We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^{\rho})$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{\rho,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.
- [9] arXiv:2611.24449 [pdf, html, other]
-
Title: Ordinal Hegselmann-Krause SystemsComments: A preliminary version will appear in the proceedings of WINE 2026Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT); Social and Information Networks (cs.SI)
We study opinion formation in the popular Hegselmann-Krause model when agents replace the traditional averaging update by a median update or more general ordinal aggregation methods. We analyze the convergence properties of synchronous and asynchronous dynamics.
For asynchronous dynamics, we show that every HKS with a $1$-Lipschitz ordinal aggregation function converges in worst-case time $\mathcal{O}(n^4)$. For the special case of median aggregation and for the family of $k\textsf{-large}$ aggregation functions, in which agents select the $k$-th largest opinion in their neighborhood, we obtain sharper bounds of $\mathcal{O}(n^3)$. For general ordinal aggregation, some sequence of $\mathcal{O}(n^2)$ updates reaches an equilibrium from every initial state. Nevertheless, other update sequences may cycle, and uniform random activation can require exponentially many updates with overwhelming probability.
For synchronous dynamics, we obtain a tight characterization. Ordinal aggregation functions satisfying the $1$-Lipschitz condition are shown to guarantee convergence in linear time. This result applies to many natural examples such as minimum, maximum, median, and $k\textsf{-large}$ functions. When the Lipschitz condition is violated, there exist instances in which synchronous dynamics do not converge at all. - [10] arXiv:2611.24526 [pdf, html, other]
-
Title: Two $(2+ε)$-Approximation Algorithms for Minimum Spanning Tree InterdictionSubjects: Data Structures and Algorithms (cs.DS)
Minimum spanning tree interdiction asks for edge deletions within a budget that maximize the weight of a remaining minimum spanning tree. We give two deterministic $(2+\epsilon)$-approximation algorithms for every fixed $\epsilon>0$, improving the previous best factor of $4$. Both algorithms respect the original budget and run in $N^{O(1/\epsilon)}$ time for $0<\epsilon\le1$, where $N$ is the binary input size. The first algorithm uses two weight thresholds to choose initial deletions that force every remaining spanning tree to contain edges at or above these thresholds. It then uses the remaining budget to further increase the MST weight through Lagrangian rounding. The second algorithm achieves the same guarantee through a different decomposition: it enumerates vertex partitions and heavy trees connecting their parts, then approximates a bounded-weight interdiction problem within the parts. An objective-preserving reduction from Maximum Components shows that, assuming the Small Set Expansion Hypothesis and $\mathsf P\ne\mathsf{NP}$, no deterministic polynomial-time $(2-\delta)$-approximation exists for any fixed $0<\delta<1$, even on simple graphs with weights in $\{0,1\}$. Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a $(4+\epsilon)$-approximation for metric-TSP interdiction.
- [11] arXiv:2611.24750 [pdf, html, other]
-
Title: Counting $6$-Cliques in $O(n^{5.97})$ time and $O(\log n)$ spaceSubjects: Data Structures and Algorithms (cs.DS)
We present an algorithm that, given read-only access to the adjacency matrix of an $n$-vertex graph $G$, computes the number of $6$-cliques in $G$ using $O(n^{5.97})$ time and $O(\log n)$ space. We achieve this by exploiting a decomposition of an equality indicator function underlying, among others, the refutations of the Exponential Time Hypothesis by OpenAI and Anthropic, and of the $k$-Clique Conjecture by Vassilevska Williams and Zamir [arXiv, 2026]. Via known reductions, this implies an $O(1.994^n)$ time and polynomial space algorithm for Max Cut on $n$-vertex graphs.
- [12] arXiv:2611.24768 [pdf, html, other]
-
Title: Small-Space Streaming Hamming ApproximationSubjects: Data Structures and Algorithms (cs.DS)
For a preprocessed pattern of length $m$ and a streaming text, we give two algorithms that estimate the Hamming distance at every alignment to relative error $\varepsilon$. They use $\varepsilon^{-8/5}m^{2/5+o(1)}$ and $\varepsilon^{-1} m^{1/2+o(1)}$ words of space, respectively, including all retained pattern information. Each estimate is reported as soon as its window ends, and all estimates are simultaneously correct with high probability. The prior space bounds are $\widetilde{O}(\varepsilon^{-3/2}\sqrt{m})$, due to Chan et al. [CGK+20], and $\widetilde{O}((m/\varepsilon)^{2/3})$, a consequence of their results and those of Clifford, Kociumaka, and Porat [CKP18]. For $\varepsilon=\Theta(m^{-a})$, the better of our two bounds improves on both prior space exponents for every fixed $0<a<1/2$.
A Fourier matcher uses $\widetilde{O}(\varepsilon^{-2}(m/K)^2)$ words to estimate each distance $d$ within $\varepsilon(d+K)$, giving relative error at most $2\varepsilon$ for $d\ge K$. A threshold matcher based on random-prime residue refinements and the multi-stream dictionary matching algorithm of Golan, Kopelowitz, and Porat [GKP18] gives our second space bound directly. Combining it with the Fourier matcher gives the first. Both space bounds extend to $L_1$ matching over polynomially bounded integer symbols. - [13] arXiv:2611.24786 [pdf, html, other]
-
Title: SotSort: a stable quicksort with a tunable bufferComments: 4 pages. Code, tests and raw measurements: this https URLSubjects: Data Structures and Algorithms (cs.DS)
SotSort is a stable comparison sort whose single code path runs with anything from a fixed 16 KB buffer to a full n-element buffer. Its core is a stable quicksort that partitions blocks through the buffer and gathers them with rotations. This report summarises the design, states which parts are borrowed, and compares an implementation against blitsort, fluxsort, glidesort, driftsort, GrailSort and WikiSort. On one 2-vCPU machine, with 32- and 64-bit integers, the constant-memory mode takes between 0.19 and 0.75 of blitsort's time on 16 of 22 input classes and between 0.94 and 1.09 on the other six. With a comparator that rules out the vector partition it is slower than blitsort on 7 of 11 classes, by up to 2.6 times on sorted input. All numbers are preliminary.
- [14] arXiv:2611.24889 [pdf, html, other]
-
Title: Improved Asymptotic Approximation Guarantees for Continuous-Review Lost-Sales and Dual-Sourcing Inventory ModelsComments: 38 pagesSubjects: Data Structures and Algorithms (cs.DS)
We study continuous-review inventory models with unit Poisson demand and deterministic lead times: single sourcing with lost sales and dual sourcing with backlogging. Xin [Operations Research. 70(1):111--128 (2022)] establishes an asymptotic approximation factor of 1.79 for each model in its proportional-growth regime. Under the same assumptions, we obtain a factor of 1.248977 for the better of base-stock and constant-order policies for lost sales and a factor of 1.599528 for the better of dual-index and tailored base-surge policies for dual sourcing. The benchmark is the optimal long-run average cost over all policies using only current and past information. For lost sales, lead time and the lost-sales penalty grow proportionally. For dual sourcing, the lead-time difference grows proportionally to the express premium, the extra unit cost of faster supply, while express lead time and backorder penalty remain fixed. For sufficiently large fixed backorder penalties, the dual-sourcing factor improves to 1.248977. The improvements follow from stronger lower bounds on the optimal cost. We retain intermediate constraints on mean inventory for lost sales and use events determined only by future demand to bound backlog costs for dual sourcing.
- [15] arXiv:2611.24905 [pdf, html, other]
-
Title: Batch-Dynamic Coreness and Applications with Logarithmic Work via Balanced PressuresSubjects: Data Structures and Algorithms (cs.DS)
We give a parallel algorithm that maintains a one-sided $(2+\varepsilon)$-approximation of all core numbers under batches of edge insertions and deletions. For fixed $\varepsilon>0$, the expected amortized work is $O(\log n)$ per edge update, and each batch has deterministic polylogarithmic depth. This improves on the previously known $(4+\varepsilon)$-approximation and $O(\log^2 n)$ amortized work bounds. This approximation factor approaches the factor-two limit for polylogarithmic update and query time under the OMv conjecture.
Our algorithm is based on assigning each vertex a "pressure" and splits each edge's unit load smoothly between its endpoints according to their pressures. After each batch of updates, our dynamic algorithm adjusts the pressures of vertices in parallel to restore balance between the pressures and loads. We show that by maintaining balanced pressures we can obtain good approximations of core numbers. Our construction also gives a $(1+\varepsilon)$-approximation of the densest-subgraph value with logarithmic expected amortized work and supports batch-dynamic maximal matching, clique counting, forest decomposition, and coloring in low-arboricity graphs with improved or matching work bounds.
We give a practical implementation of our batch-dynamic coreness algorithm and find that it is able to achieve smaller empirical error than the state-of-the-art parallel batch-dynamic implementation, while running faster. On six real-world graphs, it runs $32\times$ faster than that implementation in geometric mean and $4.1\times$ faster than a state-of-the-art heuristic baseline. On three graphs with up to 1.8 billion edges, it is $9.2\times$ faster than the heuristic baseline.
New submissions (showing 15 of 15 entries)
- [16] arXiv:2611.23387 (cross-list from quant-ph) [pdf, html, other]
-
Title: Optimal Joint Bounds for Sparse Ground-State Energy Estimation and Ground-State PreparationComments: 77 pagesSubjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
Ground-state energy estimation (GSEE) and ground-state preparation (GSP) are fundamental problems in quantum computing. Given a Hamiltonian $H$ with $\|H\|\le1$ and a guiding state $|\psi\rangle$ with overlap at least $\gamma>0$ with the ground space of $H$, the goal in GSEE is to estimate the ground-state energy of $H$ to additive error $\delta$ with failure probability at most $\varepsilon$, while in GSP it is to prepare a state with ground-space weight at least $1-\varepsilon$, given a gap lower bound $\Delta$. Their costs are measured by quantum query complexity, i.e., the number of oracle calls needed to access $H$. Recent work proved optimal bounds $\Theta(\log(1/\varepsilon)/(\gamma\delta))$ for GSEE and $\Theta(\log(1/\varepsilon)/(\gamma\Delta))$ for GSP in the time-evolution and block-encoding models. However, these models do not directly account for the sparsity of $H$, measured by the maximum number $s$ of nonzero entries in any row or column. In the sparse-access model, oracles instead return the locations and values of these entries. This introduces the additional parameter $s$, and it remained open how query complexity depends jointly on $s$, $\gamma$, $\delta$ or $\Delta$, and $\varepsilon$. We resolve this by proving sparse-query lower bounds $\Omega(\sqrt{s}\log(1/\varepsilon)/(\gamma\delta))$ for GSEE and $\Omega(\sqrt{s}\log(1/\varepsilon)/(\gamma\Delta))$ for GSP, even for stoquastic Hamiltonians. We also show that these constructions recover the earlier time-evolution and block-encoding lower-bound scalings. We then give matching upper-bound algorithms in the reversible in-place sparse-location model. Thus, we obtain $\Theta(\sqrt{s}\log(1/\varepsilon)/(\gamma\delta))$ for GSEE and $\Theta(\sqrt{s}\log(1/\varepsilon)/(\gamma\Delta))$ for GSP, showing that $\sqrt{s}$ is necessary and sufficient and completing the joint dependence on all problem parameters.
- [17] arXiv:2611.23431 (cross-list from math.PR) [pdf, html, other]
-
Title: The Spectral Distribution of Matrix Least Squares Solutions, and the Ellipsoid Fitting ProblemComments: 40 pagesSubjects: Probability (math.PR); Data Structures and Algorithms (cs.DS); Statistics Theory (math.ST); Machine Learning (stat.ML)
We study the spectral distribution of the least squares solution to a random linear system whose unknown is a symmetric matrix. In the normalized and isotropic setting, we derive a closed-form description of the support of the spectral distribution. As an application, we consider the ellipsoid fitting problem: given $n$ standard Gaussian vectors in $\mathbb{R}^d$, does there exist a centered ellipsoid passing through all of them? It was recently shown that this problem has a sharp phase transition at $n \approx d^2/4$. On the satisfiability side, unlike earlier results, these sharp results do not rely on least squares candidates. We show that the least squares candidates considered in earlier works have a threshold of positive semi-definiteness at $n \approx d^2/10$, which was previously observed numerically and predicted non-rigorously using statistical physics methods. Moreover, we show that the corresponding least squares dual certificates have a threshold of positive definiteness at $n \approx 2d^2/5$. Our approach combines several matrix concentration tools. A key technical ingredient, which may be of independent interest, is showing that a certain kernel matrix is well-conditioned with high probability until $n \approx d^2/2$.
- [18] arXiv:2611.23617 (cross-list from cs.LG) [pdf, html, other]
-
Title: Error accumulation in reverse diffusion with an imperfect score: beyond path-space analysesSubjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Probability (math.PR)
Diffusion modeling is a popular method of sampling from a complex, high-dimensional distribution $p$ using learned approximations of its (noised) score functions. Generating a single sample requires simulating the reverse diffusion process, which requires many queries to the learned scores. Thus, a priori, the learning errors can easily compound. Indeed, in existing theoretical analyses, the sampling error (as measured in total variation distance to $p$) accumulates polynomially with the horizon of the stochastic process. This is a consequence of bounding the error of the output law by the error of the law of the entire reverse diffusion path.
In this paper, we demonstrate that by circumventing the "path-space" analysis, the error accumulation of the diffusion sampler can be mitigated when $p$ satisfies a Poincaré inequality. Moreover, we achieve this result as a special case of a broader framework that applies to any distribution $p$, but relaxes the error metric from total variation distance to a weaker metric capturing all sample statistics that do not "witness" the multimodality of $p$.
We then zoom out from analyzing the diffusion sampler to the information-theoretic question: given a learned score with some error bound, how accurately can we identify $p$? We show that, for any given bound on the Poincaré constant of $p$, the diffusion sampler already nearly achieves optimal total variation error. - [19] arXiv:2611.24167 (cross-list from cs.GT) [pdf, html, other]
-
Title: On the Complexity of Envy Cycle EliminationSubjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
The envy cycle elimination (ECE) algorithm is a fundamental algorithm for the fair allocation of indivisible goods, guaranteeing an allocation that is envy-free up to one good under arbitrary monotone utilities. We show that the ECE algorithm can be implemented in $O(nm)$ time for $n$ agents and $m$ goods, and establish the tightness of this bound.
- [20] arXiv:2611.24181 (cross-list from stat.ML) [pdf, html, other]
-
Title: Rare-Tail Statistics For Learning Biased Gaussian Halfspaces with Label NoiseComments: NeurIPS 2026, to appearSubjects: Machine Learning (stat.ML); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST)
We revisit the classical problem of learning general Gaussian halfspaces in the presence of label noise, with particular focus on the large-bias regime, where information-computation gaps are conjectured in several standard label-noise models. Concretely, we present and analyze the rare-tail mean estimator, an extremely simple one-shot statistic that averages only the observed minority class. In the large-bias regime, classical Averaging (Servedio, 1999) and related global first-moment statistics are provably suboptimal, while the rare-tail mean estimator recovers the target halfspace direction at the information-theoretic sample rate (modulo log factors) under a broad class of label noise models, including probit noise and margin-dependent noise with very slow decay away from the boundary. Notably, our guarantees allow labels arbitrarily close to the decision boundary to be nearly random, while still giving strong directional recovery from a small number of samples. The estimator also cleanly interpolates between the noiseless and noisy regimes: without noise, it attains the same sample rate as classical separability-based methods for realizable halfspaces, and under low noise, or noise that decays away from the boundary, it keeps this rate even after linear separability has been destroyed. As an application, we consider a two-stage curriculum in which source samples, whose noise may be arbitrarily close to $1/2$ near the boundary and decay very slowly away from it, precede target samples, whose noise flips every label at the same rate, i.e., random classification noise (RCN). Since both stages share the same Bayes optimal halfspace, our estimator supplies the directional warm start needed by existing refinement routines, and together they learn the RCN target at the information-theoretic sample rate in the large-bias regime, up to log factors.
- [21] arXiv:2611.24611 (cross-list from cs.CG) [pdf, html, other]
-
Title: Inapproximability of Euclidean Steiner TreeComments: 40 pages, 19 figures. Abstract shortened to comply with arXivs length limitSubjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
We consider the Euclidean Steiner Tree problem of connecting $n$ given points in $\mathbb{R}^d$ by a shortest network allowing the addition of Steiner points anywhere in the space. Arora [FOCS'96/'97, J. ACM'98] gave a polynomial-time approximation scheme (PTAS) for Euclidean Steiner Tree and TSP in every fixed dimension, and Trevisan [STOC'97, SICOMP'00] proved that Euclidean TSP is APX-hard in $O(\log n)$ dimensions. They left open whether Euclidean Steiner Tree admits a PTAS in high dimension. Our first contribution settles this thirty-year-old question by proving APX-hardness in $O(\log n)$ dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP $\not\subseteq $SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in $O(\log\log n)$ dimensions. This dimension bound is tight up to a factor of $O(\log\log\log n)$, since Arora's scheme is a PTAS in up to $\log\log n/\log\log\log n$ dimensions.
In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time $2^{O_d(\varepsilon^{-(d-1)})}n\log n$ and proved matching Gap-ETH lower bounds for Euclidean TSP and Rectilinear Steiner Tree, but left a corresponding lower bound for Euclidean Steiner Tree as an open question. Our second contribution answers this question with a nearly tight lower bound on the dependence on accuracy for Euclidean Steiner Tree. However, given the recent claimed refutations of ETH and hence Gap-ETH by OpenAI and Anthropic, we use the weaker assumption that 3SAT has no truly subexponential-time algorithm, that is, no $2^{n^\gamma}$-time algorithm on formulas of size $n$ for any constant $\gamma<1$ (a hypothesis one might call weak ETH). Under this assumption, we prove that no $(1+\varepsilon)$-approximation algorithm runs in time $2^{O(\varepsilon^{-\gamma(d-1)})} poly(n)$ for any such $\gamma$.
Cross submissions (showing 6 of 6 entries)
- [22] arXiv:2602.13861 (replaced) [pdf, html, other]
-
Title: Min-Max Connected Multiway CutSubjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Optimization and Control (math.OC)
We introduce a variant of the multiway cut that we call the min-max connected multiway cut. Given a graph $G=(V,E)$ and a set $\Gamma\subseteq V$ of $t$ terminals, partition $V$ into $t$ parts such that each part is connected and contains exactly one terminal; the objective is to minimize the maximum weight of the edges leaving any part of the partition. This problem is a natural modification of the standard multiway cut problem and it differs from it in two ways: first, the cost of a partition is defined to be the maximum size of the boundary of any part, as opposed to the sum of all boundaries, and second, the subgraph induced by each part is required to be connected. Although the modified objective function has been considered before in the literature under the name min-max multiway cut, the requirement on each component to be connected has not been studied as far as we know. Our main motivation for studying this problems is its close connection with the spanning tree congestion problem that has been extensively studied but on which little progress has been made.
We show various hardness results for this problem, including a proof of weak NP-hardness of the weighted version of the problem on graphs with treewidth two, and $W[1]$-hardness for the problem when parameterized by the treewidth of the graph. Complementing our lower bounds tightly, we also provide a pseudopolynomial time algorithm as well as an FPTAS for the weighted problem on graphs of bounded treewidth. As a consequence of our investigation we also show that the (unconstrained) min-max multiway cut problem is NP-hard even for three terminals, strengthening the known results. - [23] arXiv:2609.24804 (replaced) [pdf, html, other]
-
Title: FPT Isomorphism Test for $F$-Free TournamentsComments: 18 pages; second version adds missing attribution of earlier results and improves the write-upSubjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test.
Our algorithm builds on a combination of spectral, geometric, combinatorial and group-theoretic tools. - [24] arXiv:2611.07622 (replaced) [pdf, html, other]
-
Title: Approximate Hamming Convolution via Rectangular Matrix MultiplicationSubjects: Data Structures and Algorithms (cs.DS)
We study $(1 \pm \epsilon)$-approximate text-to-pattern Hamming distance: given a length-$N$ pattern and a length-$2N$ text, compute the Hamming distance at every alignment to relative error $\epsilon$. For every fixed $a \ge 0$ and $\epsilon = N^{-a}$, we give a randomized algorithm with simultaneous high-probability correctness on a logarithmic-word RAM and expected running time $\widetilde{O}(N^{\omega(4a)/2})$, where $\widetilde{O}$ suppresses subpolynomial factors and $\omega(k)$ is the exponent for multiplying an $n \times n^k$ matrix by an $n^k \times n$ matrix. With a recent rectangular bound, this improves the published bounds [CGK+20, FKN26] for $1/12 < a < (3 + \sqrt{3})/16$. In particular, the algorithm runs in expected time $\widetilde{O}(N)$ for $0 \le a \le 1/8$, extending the previous near-linear guarantee through $a = 1/12$.
- [25] arXiv:2611.17050 (replaced) [pdf, html, other]
-
Title: Finding the Farthest in High Dimensions: Dynamic Diameter and Farthest-Neighbor SearchSubjects: Data Structures and Algorithms (cs.DS)
We give algorithms for maintaining diameter in the dynamic model, and for answering farthest-neighbor queries on a fixed point set, in high-dimensional Euclidean space. For every fixed $1<c<\sqrt2$, update horizon $t$, and error probability $\delta$, we maintain an actual factor-$c$ diameter pair with worst-case update time $n^{2/c^2-1}\text{poly}_c(d,\log(2nt/\delta))$ and space $n^{2/c^2}\text{poly}_c(d,\log(2nt/\delta))$. Here $n$ bounds the number of active point identities. The update exponent improves Indyk's SODA~2003 bound from $1/c^2$ to $2/c^2-1$, while the space exponent improves from $1+1/c^2$ to $2/c^2$. At $c=\sqrt{3/2}$, the update exponent decreases from $2/3$ to $1/3$. A separate construction achieves approximation exactly $\sqrt2$ with update time polynomial in $d$ and $\log(2nt/\delta)$. With probability at least $1-\delta$, every maintained answer during the first $t$ updates is correct, even when updates depend on all previous answers and random choices.
A second construction improves the update exponent when the space exponent is close to one. On rational inputs, it has an always-correct variant with expected amortized update bounds over every fixed finite prefix of an adaptive execution, without an advance update horizon. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time.
The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation $\sqrt2-\varepsilon$, the diameter time is $n^{1+O(\varepsilon)}$, and the query time is $n^{O(\varepsilon)+o(1)}$ with near-linear preprocessing and space, up to polynomial input-parameter factors. - [26] arXiv:2611.21294 (replaced) [pdf, html, other]
-
Title: Constant-Factor Matching-Size Estimation in Random-Order StreamsSubjects: Data Structures and Algorithms (cs.DS)
We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using $O(\log^2 n)$ bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least $2/3$, does not require the number of edges in advance, and has worst-case total running time $O((m+1)\log(n+2))$ on a word RAM.
Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an $O(\log^2 n)$-approximation in random order. We obtain a constant factor in the latter model with the same $O(\log^2 n)$ space bound.
The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack. - [27] arXiv:2201.02514 (replaced) [pdf, html, other]
-
Title: Efficiency of ANS Entropy EncodersComments: 27 pages, 5 figures, 1 table, 2 listingsSubjects: Information Theory (cs.IT); Data Structures and Algorithms (cs.DS)
Asymmetric Numeral Systems (ANS) is a class of entropy encoders that had an immense impact on the data compression, substituting arithmetic and Huffman coding. It was studied by different authors but the precise asymptotics of its redundancy (in relation to the entropy) was not completely understood. We obtain optimal bounds for the redundancy of the tabled ANS (tANS), the most popular ANS variant. Given a sequence $a_1,a_2,\ldots,a_n$ of symbols from an alphabet $\{0,1,\ldots,\sigma-1\}$ such that each symbol $a$ occurs in it $f_a$ times and $n=2^r$, the tANS encoder using Duda's ``precise initialization'' to fill tANS tables transforms this sequence into a bit string of the following length (the frequencies are not included in the encoding): $\sum\limits_{a\in[0..\sigma)}f_a\cdot\log\frac{n}{f_a}+O(\sigma+r)$, where $O(\sigma+r)$ can be bounded by $\sigma\log e+r$. The $r$-bit term is an artifact indispensable to ANS; the rest incurs a redundancy of $O(\frac{\sigma}{n})$ bits per symbol. We complement this by examples showing that an $\Omega(\sigma+r)$ redundancy is necessary. We argue that similar examples exist for most adequate initialization methods for tANS. Thus, we refute Duda's conjecture that the redundancy is $O(\frac{\sigma}{n^2})$ bits per symbol. We also propose a variant of the range ANS (rANS), called rANS with fixed accuracy, parameterized by $k\ge 1$ that in certain conditions might be faster than the standard rANS because it avoids slow explicit division operations. We bound the redundancy for our rANS variant by $\frac{n}{2^k-1}\log e+r+k$.
- [28] arXiv:2505.02977 (replaced) [pdf, html, other]
-
Title: Tackling Parallelization Challenges of Randomized Preconditioners With Dependency TrackingTianyu Liang, Chao Chen, Yotam Yaniv, Hengrui Luo, David Tench, Xiaoye S. Li, Aydin Buluc, James Demmel, Jie ChenSubjects: Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS); Numerical Analysis (math.NA)
Incomplete Cholesky (IC) preconditioners are the standard black-box, memory-efficient first resort for large graph Laplacian systems, but classical IC can break down on irregular graphs. Approximate Cholesky (AC) addresses this with randomized dropping that is provably breakdown-free. Its stochastic fill-in pattern, however, resists static parallelization, creating a "setup bottleneck." We present ParAC, which parallelizes the sequential rchol algorithm on CPUs and GPUs using dynamic dependency tracking and architecture-aware memory management, without altering its numerics. Total time-to-solution speedups over deterministic IC reach $57.3\times$ on CPU and $52.2\times$ on GPU. Algebraic multigrid (AMG) remains preferable on structured PDE discretizations; on irregular graph Laplacians where AMG struggles, ParAC attains up to $7.2\times$ and $6.0\times$. On 200 adversarial SDD systems, ParAC converges on every instance, whereas the AMG solvers fail on 15 and 19, on CPU and GPU, respectively.
- [29] arXiv:2607.07085 (replaced) [pdf, html, other]
-
Title: Is Randomness Necessary for Adaptive Data Analysis?Comments: Contains a new proof in the plain model, using domain of size 2^{poly(n)}Subjects: Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing $n$ i.i.d. samples from an unknown distribution $\mathcal{P}$ over a domain $\mathcal{X}$, and our goal is to answer a sequence of $k$ adaptively chosen statistical queries with respect to $\mathcal{P}$. The main question is how many queries we can support (i.e., how large $k$ can be), primarily as a function of the number of samples $n$. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support $k \approx n^2$ queries, and no computationally efficient mechanism can answer $k \gg n^2$ queries. In this paper, we address a fundamental question: is randomness necessary for ADA?
Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is {\em not} necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic setting. Perhaps surprisingly, we show that randomness is {\em strictly necessary} to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just $k = \tilde{O}(n)$ queries. - [30] arXiv:2609.06318 (replaced) [pdf, html, other]
-
Title: A 5/3 Guarantee for Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial SystemsComments: 33 pages of main text and references, plus a 32-page online appendix; 6 figuresSubjects: Optimization and Control (math.OC); Data Structures and Algorithms (cs.DS)
Fixed shipment costs encourage large orders, while inventory and customer backlog costs favor frequent replenishment. In a serial system, the stages must also coordinate their lot sizes and material availability. We study the classical echelon stock $(R,nQ)$ policy: the downstream stage requests a fixed lot, the upstream stage orders an integer multiple of that lot, and transfers contain complete lots. For unit Poisson demand, full backlogging, and at both stages, deterministic lead times, and setup and holding costs, we prove that the optimized cost in this class is at most $5/3\approx1.667$ of the optimal admissible system cost, uniformly over all nonnegative cost rates, demand rates, and lead times. The guarantee holds even when the selected policy pays a setup charge for every lot while the optimal benchmark pays only once per aggregate shipment. To obtain the guarantee, we use a common inventory calculation that allows independently chosen replenishment frequencies while respecting upstream material availability. We compare its optimized value, an upper bound on the best integer-ratio policy cost, with a novel lower bound on the optimal system cost that combines allocated single-stage costs with the minimum inventory cost when setup costs are zero. We also show that no uniform factor below $(1+\sqrt{3})/2\approx1.366$ is possible for the classical class. Existing numerical experiments place best-found classical policies within $22.7\%$ of an evaluated lower bound across three broad grids. The results quantify both the reliability and the limits of a simple operating rule and explain how shipment consolidation, replenishment timing, and flexibility affect its value.
- [31] arXiv:2609.37118 (replaced) [pdf, html, other]
-
Title: Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time SolvableSubjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids $P_k\square P_n$ with at most three colors. For every fixed height $k$, it computes the minimum number of moves and an optimal sequence in $N^{O(k^2)}$ time, where $N=kn$. This resolves the previously open three-color case on complete \(3\times n\) boards.
The proof uses a representation of flooding strategies as paintings by connected regions. We show that an optimal painting can be chosen so that its regions form a rooted tree with strong restrictions on the colors along ancestral paths. These restrictions make the part of the tree visible in any fixed-size connected window admit only polynomially many descriptions. The remaining common ancestors may form an arbitrarily long chain. We retain that chain on a stack and use a finite context-free recurrence to minimize the total painting cost without enumerating all possible stack contents. Connectivity information at the boundary ensures that the resulting local descriptions assemble into one valid global painting.
The argument also applies to graphs supplied with an ordering into connected layers of bounded size, provided every edge lies within one layer or joins consecutive layers, and consecutive layers are joined by an edge. For a family of three-row boards, every optimal admissible painting tree has a common-ancestor chain of depth linear in the board width.
For any fixed height and palette size, we give a deterministic EPTAS via a separate budget-parameterized algorithm, and we show that no FPTAS exists for $k\geq 3$ with at least four colors unless P = NP.
We also provide a solver for \(3\times n\) boards, implemented with AI assistance based on the algorithm described in this paper. The implementation is available at GitHub - [32] arXiv:2611.01028 (replaced) [pdf, html, other]
-
Title: Shared Randomness and Parallel Rounds in Permutation SamplingSubjects: Information Theory (cs.IT); Data Structures and Algorithms (cs.DS)
Sampling a uniformly random permutation of $[n]$ in parallel is a coordination problem: $n$ processors, one per coordinate, must output distinct values. A single round requires a shared seed of $\log n!$ nats, while $n$ rounds require no shared randomness. We determine the tradeoff in between for $R$ rounds, in which the values of each round are written independently given the shared randomness and the earlier output, and the output must be a uniform permutation, exactly or within total-variation error $\varepsilon$. Shared randomness is measured by its support size or by its entropy, and it is either fixed in advance or drawn adaptively during the execution.
For exact sampling, all four costs equal one explicit combinatorial quantity up to an absolute additive constant. A fixed error $0<\varepsilon<1$ shortens the seed by $O(1)$ nats in one round, where the least number of seed values, an approximate nonnegative tensor rank, is $(1-3\varepsilon/2)\,n!$ up to an additive two for $\varepsilon\le1/2$. The saving is $\Theta((\log n)^2)$ nats in two rounds, with a sharp constant, and of lower order for $R=o(n)$; for $R\sim\rho n$ with $0<\rho<1$ it is linear in $n$, with the optimal rate given by a variational formula. Here, errors above an explicit threshold need only $o(n)$ nats, and at every positive error below it, shared randomness drawn adaptively has strictly smaller entropy than a seed fixed in advance. A central tool is a change of measure that turns lower bounds with error into entropy bounds for a single batch of distinct, nearly independent values. The results for sublinearly and linearly many rounds extend to sampling without replacement.