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 3
Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces
We develop a unified algorithmic framework for computing approximate minimum spanning trees (MSTs) in metric spaces in the fully scalable Massively Parallel Computation (MPC) model.Efficient Stable Word-RAM Simulation by Population Protocols
Population protocols model computation by indistinguishable agents interacting in uniformly random pairs, with unary inputs and outputs encoded by state counts.Sublinear Approximations for Spanning Tree Congestion
The spanning tree congestion of a connected graph \(G\) is the minimum, over all spanning trees \(T\) of \(G\), of the maximum number of edges of \(G\) crossing a cut induced by deleting an edge of…Consistent Submodular Maximization with Full Foresight
Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes.A Dichotomy for Terminal Cyclability
Given an undirected graph $G$ and a set $R \subseteq V(G)$ of terminals, Terminal Cyclability asks whether $G$ contains a simple cycle visiting every vertex of $R$.A Polynomial Erdős-Pósa bound for Eulerian digraphs
In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property.Estimating the Volume of a Union of Convex Bodies
The \textit{Union Volume Estimation problem}, i.e. yielding an $(\varepsilon, δ)$-approximation of the volume of the union of convex bodies, is a classical problem in computational geometry and…Partially Dynamic Algorithms for Single-Source Temporal Paths
We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with $n$ vertices.Polynomial $(2α+\varepsilon)$- and Quadratic $4$-Approximation Algorithms for the Biased Traveling Salesman Problem in Bipartitioned Networks
The traveling salesman problem (TSP) is one of the fundamental problems in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices.Beyond Gomory-Hu: All-Pairs $\times$ All-Pairs Mincuts in $O(n)$ Space
For over four decades, two classical structures have offered complementary views of mincuts.Computing Forest Degree Realizations with Minimum Cardinality Domination
In the Degree Realization problem with respect to a family $\mathcal{P}$ of graphs the input is a non-increasing sequence $d = (d_1,\ldots,d_n)$ of positive integers, and the goal is to decide…A $2.81^n$ upper bound on the number of stable matchings
We study the maximum number ${\rm SM}(n)$ of stable matchings in an instance with $n$ men and $n$ women.A Sub-$3^n$ Upper Bound on the Number of Stable Matchings
We study the problem of determining the maximum number of stable matchings.Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL
We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update.Dimension-Free Private Mean Estimation is Impossible Without the Covariance
We study the limits of differentially private Gaussian mean estimation when the covariance matrix is unknown.Deterministic Connectivity Sketches Under Edge Deletions
How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions?Approximating #BIS in $\exp(\widetilde O(n^{1/3}))$ Time
We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS).Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error
We give a polynomial-time $(\varepsilon, δ)$-edge-differentially private algorithm that releases a synthetic graph approximately preserving all cut values of a nonnegative weighted input graph $G$.The Online $k$-Taxi Problem Is Competitive on All Metrics
The online $k$-taxi problem is a natural generalization of the $k$-server problem: $k$ taxis must serve a sequence of requests in a metric space.Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time
For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time.