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 28
The Online Steinitz Problem
Inspired by Steinitz's celebrated result (1913) and recent online vector-balancing results of Kulkarni et al. (2024) and Aden-Ali (2026), we introduce the online Steinitz problem: $T$ vectors in…A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
Submodular maximization arises in a wide range of combinatorial optimization problems and has been extensively studied from the perspective of approximation algorithms.Improved Massively Parallel Shortest Path Computation
We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model.Tight Approximations for Fixed-Order Vehicle Routing with Stochastic Demands
We study the vehicle routing problem (VRP) with stochastic demands, where each client has an independent demand with a known distribution, and its realized demand is observed only on the first visit.The Communication Complexity of the Coin Problem
We study the two-player communication complexity of the \textsf{Coin} problem.Tractability of Hard Digraph Cut Problems on Eulerian Instances: Treewidth Reduction and Reducing CMSO to Unbreakable Eulerian Instances
Eulerian digraphs retain the directional structure of general digraphs while exhibiting a symmetry of cuts reminiscent of undirected graphs.Approximation Algorithms for Graphic Multi-Depot TSP and Graphic Multi-Path TSP
We give improved approximation algorithms for two graphic TSP variants.Exponential Local Search in Bounded-Occurrence MAX-CSP
We study the number of improving steps that local search may require for $(2,2,r)$-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every…Can Rényi Accountants Beat Lossless Accountants for DP-SGD?
Recent frameworks in differential privacy (DP), such as privacy loss distributions and $f$-DP, provide lossless representations of the privacy leakage of mechanisms.LOCAL LLL in $\operatorname{poly}(\log\log n)$ Rounds
We provide a $\operatorname{poly}(\log\log n)$-round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion $pd^{c} < 1$, for a sufficiently large constant $c$.Parameterized algorithms for representing graphs as intersections of threshold graphs
A graph is called a threshold graph if there is an assignment of real valued weights to its vertices such that two vertices have an edge between them if and only if the sum of the weights of the two…A Better-than-$2$ Approximation for $k$-Median Part II: Stable Instances
We consider the $k$-median problem on general metric spaces, subject to the condition that the instances are $β$-stable (i.e., the optimal solution using $k-1$ centers has a cost at least $(1+β)$…Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More
We give a new rounding technique for spreading-metric linear programs, called Greedy Region Growing, which adapts the classical technique of region growing to min-max graph layout problems and…Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions.Fast Forgiving Base64 Decoding with SIMD Instructions
On the Internet, we use the Base64 format to represent binary data (e.g., images or cryptographic keys) as text.Thin matrix products up to D <= N^0.172 and lossless reductions for 3SUM, Exact Triangle and APSP, with 3SUM over abelian groups and a dichotomy for coordinatewise problems
Alman and Vassilevska Williams (arXiv:2610.06783) gave the first polynomial improvements over the textbook algorithms for 3SUM and APSP: deterministic algorithms with exponents 1.9992 for 3SUM…Cascade: GPU-Accelerated Out-of-Core Suffix Array Construction for LLM Corpora
Suffix arrays over LLM (pre)training corpora underpin deduplication, contamination testing, n-gram statistics, and training-data attribution, and every new corpus or tokenizer needs a new one.Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds
Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in…Optimal High Probability Bounds for Random Order Online Sorting
In random order online sorting, a fixed multiset of $n$ real numbers arrives in a uniformly random order.FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood.