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 7
Quantum Query Lower Bounds from Classical Moment Matching
We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing.Recognizing Label-Connected Graphs
In classical gossiping, each participant initially knows a distinct piece of information.Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms
Using the bisection bound of Monien and Preis, Fomin and Høie proved in 2006 that every graph of maximum degree 3 on $n$ vertices has pathwidth at most $n/6+o(n)$.Logarithmic Embeddings into Probabilistic Spanning Trees for Distances and Capacities
We prove that every connected $n$-vertex graph admits a probabilistic embedding into its spanning trees with expected distance stretch $O(\log n)$.Efficient Equilibrium Computation in Colonel Blotto Games
Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value.Beyond the Bochner Method: Optimal Spectral Gaps for Block Dynamics of Spin Systems like the $O(N)$ Model
Let $μ$ be a probability distribution on a spin system with $n$ sites and possibly infinite spin spaces.Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations
We study max-min allocation (the Santa Claus problem) and weighted Nash social welfare for $n$ agents with subadditive valuations over $m$ indivisible items.Catalan Hashing: Efficient Linear Probing for Variable-Length Items
A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous…Gaussian Partitioning for Reliable Learning of Multi-Index Models
We introduce Gaussian partitioning, an algorithmic primitive for distributions smooth with respect to a Gaussian.Roundtrip All-Pairs Shortest Paths in Directed Graphs
We study approximation algorithms for All-Pairs Shortest Paths (APSP) in directed graphs under the roundtrip metric.Agnostic Learning by Imitating
Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive…Breaking the quantum barriers for Graph Collision
In the graph collision problem, the task is to decide whether a known graph on $n$ vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked…A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model
Montanari's incremental approximate message passing (IAMP) algorithm [FOCS 2019; SIAM J. Comput., 2025] and the zero-temperature formulation of El Alaoui, Montanari and Sellke (AMS) [Ann.Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations
The Multiway Cut problem is among the most well-studied problems in the area of combinatorial approximation algorithms.Fast Quantum Byzantine Agreement with Nearly Linear Quantum Communication
We consider synchronous binary Byzantine agreement among $n$ processes connected by authenticated point-to-point classical and quantum channels.Private Online Release of Adaptive Linear Queries
In this paper we study answering counting and other linear queries online under differential privacy constraints.The Harmonic Online $k$-Server Algorithm Is Poly(k)-Competitive
The online $k$-server problem is one of the most fundamental problems in online algorithms.Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness
The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices.Incremental Minimum Spanning Trees on a Napkin
In the incremental minimum spanning forest problem, weighted edges arrive one at a time.Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation
\emph{Text-to-Pattern Hamming Distances} is one of the most studied problems in string algorithms: given a text $T$ of length~$n$ and a pattern~$P$, the task is to compute the Hamming distance…