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 5
Metric TSP in Sublinear Time: Breaking Two Approximation
The seminal result of Czumaj and Sohler [STOC'04] showed that a 2-approximation of the value of metric TSP can be obtained with sublinear queries.State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities.Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling
We give classical randomized algorithms in a word RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP).XOR-Functions and Beyond in the Random Query Model
We study time--space tradeoffs for computing Boolean functions $f:\{0,1\}^n \to \{0,1\}$ in the random query model.Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints
We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of $v$-vertex simple graphs with failure probability at most $δ$.Binary Huffman Coding with Unequal Letter Costs Is NP-Complete
Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost.Entropy-Weighted Soundness for Multi-Answer Birthday Graphs
The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables.Dynamic Steiner Tree under Edge Updates
The Steiner tree problem is the canonical generalization of minimum spanning tree (MST).Distributionally Robust Search: The Power of Information and the Limits of Moments
We study binary search for a target drawn from a distribution on $n$ ordered elements.Abelian embeddings make useful promises: approximation of detrivialised equations
We study the following family of search problems: given a system of equations $x+y+z\equiv 0\pmod p$ promised to admit a solution that is nonconstant on every equation, find a $c$-colouring of the…First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs
We present the first four All-Pairs Approximate Shortest Paths (APASP) algorithms for decremental weighted undirected graphs.Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models
We show that for every $γ>0$ and every sufficiently large $Δ$, the Glauber dynamics for proper $q$-colorings of any $n$-vertex graph of maximum degree $Δ$ has spectral gap $Ω_γ(1/n)$, and hence…Pure Differentially Private Query Release via Laplace Input Smoothing
We study the offline release of a public family of $k$ statistical queries on a database of $N$ records from a public universe of size $d$, under pure $\varepsilon$-differential privacy.Finding Integer Roots of Polynomials in Nearly Optimal Time
Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$.Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners
In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to $O(kn^{1/k})$ trees in expectation, and every pair…Smallest Multiplicative Stretch for an $α$-APASP Below $\widetilde O \left(n^ω\right)$ Runtime
Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2-\varepsilon)$-APASP is at least as hard as BMM for every fixed $0<\varepsilon<1$.Approximation Algorithms for Multi-Criteria Network Design Problems
Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across…Optimal (Randomized) Compact Routing Schemes
Compact routing schemes route messages along short paths while every vertex stores little information.Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds
Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance.Differentially Oblivious Priority Queues with Sublogarithmic Cost
In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model.