Theory & Algorithms · Computer Science & AI
Data Structures & Algorithms
The newest papers in Data Structures & Algorithms that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
1,174 papers, from 4 September 2026 to 5 November 2026: 1,174 arXiv preprints.
Get the few papers worth your time in Data Structures & Algorithms every morning.
Follow Data Structures & Algorithms and ReadSearch reads its new papers each day, then brings you the few worth reading, each with its key finding in a sentence.
Newest papers, page 45
Fast Spectral Signing for Vector Balancing
The Komlós conjecture, now a theorem, asserts that whenever the columns of a matrix $A\in\mathbb{R}^{m\times n}$ have Euclidean norm at most one, some signs $\varepsilon\in\{-1,1\}^n$ make every…Strongly Refuting Semirandom Linear Systems in Subexponential Time
In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides.Move-rb: Faster Bi-Directional r-indexes and Approximate Pattern Matching
Approximate pattern matching (APM) on highly repetitive texts is a central task in bioinformatics.Optimal spectrum estimation
We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log…Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets
The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number $z$ of phrases that each refer to an earlier occurrence.A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model.Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least $\frac{25200}{46189}n>0.5455\,n$ leaves.Settling the Matroid Secretary Problem
This paper settles the Matroid Secretary Problem with an $e$-probability-competitive algorithm.Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at $β< 1$
We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with $o_n(1)$ error in total-variation distance (TVD) at any inverse-temperature $β< 1$.Matrix-Vector Complexity of Low-Rank Approximation
We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products.Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
We study exact pattern matching on indeterminate strings, where a text or pattern position may represent a set of symbols rather than a single letter.$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
When designing algorithms for geometric graphs, exploiting structural parameters can lead to significantly improved bounds.Sampling Line-Graph Colorings with Constant Extra Colors
Let $G$ be the line graph of a finite simple graph, with $n\geq1$ vertices and maximum degree $Δ$.Vertex-Coloring Edge-Weighting: Kernelization and Generalization
An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it.Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
One item set evaluated at two capacities $R<D$ produces two concave hulls of optimal value against cardinality.Homological Trimming and Regularity of Filtrations via Local Obstruction Modules
Existing link-based combinatorial preprocessing methods speed up the computation of persistent homology by removing a vertex or edge only when its link remains a cone.Personalised versus Posted Pricing from Samples
Personalised pricing maximises expected revenue from a market but requires detailed information about individual customers.A 27 x 27 x 27 counterexample to Comon's conjecture
We report an explicit construction of a 27 x 27 x 27 symmetric tensor with rational entries that has tensor rank 55 over the rational numbers and symmetric tensor rank 56 over the complex numbers…Transposition achieves OPT$+O(1)$ in polynomial time for IID list update
In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$.Hutch#: Optimal non-adaptive Frobenius norm estimation
The Girard--Hutchinson estimator provides an extremely simple randomized estimate of the Frobenius norm of a matrix $A$ that can only be accessed implicitly via matrix-vector products.