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 29
Approximation Algorithms for Dual-Memory Request Scheduling in Disaggregated LLM Inference
Disaggregated LLM inference executes the prefill and decode phases on separate resource pools, reducing interference between the two phases.Almost Lossless Transfer for Cuttable Distributed Problems
We study constant-round LOCAL approximation for additive local vertex-subset minimization problems.Metric Planarity Testing is Hard
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing.DualColl: Throughput-Optimal Bandwidth-Bound Collective Communications via Fractional Tree Packing
Large-scale distributed training increasingly makes collective communication bandwidth-bound.Adaptive Robust Confidence Sets in High Dimensions
We study adaptive confidence sets for mean vectors of multivariate Gaussians with identity covariance under Huber contamination when the contamination proportion is unknown.Exact and Asymptotic Analysis of Greedy Online Facility Assignment on Cycle Metrics
We identify the free-facility gaps of greedy online assignment on a cycle with the discrete additive coalescent and use this connection to determine the exact expected assignment cost.Fair Allocation with Dichotomous Preferences over Item Complements
We study the problem of fair allocation when agents have dichotomous submodular preferences over groups of, rather than individual, items.Adaptive Sorting, also in the BST Model
Sorting is one of the most basic algorithmic problems.Social Learning of Ranking: Getting the Top Right despite Local Herding
In sequential learning, a group of agents sequentially receives a noisy private signal and observes the predictions of prior agents to estimate a hidden ground truth.Sample-Optimal Multi-Group Learning with an ERM Oracle
In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations.Faster Deterministic Approximation for Counting Knapsack
Given $n$ nonnegative integer weights $w_1, \ldots, w_n$ and an integer knapsack capacity $T$, the $\#$Knapsack problem asks to count the number of subsets $I \subseteq \{1, 2, \dots, n\}$ such that…The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation
Consider an unknown graph $G = (V,E)$ with vertex degrees $d_v$, accessed only by sampling uniformly random edges and querying the degrees of their endpoints.Random Fourier Features in Near-Linear Time
Random Fourier features approximate a shift-invariant kernel in $\mathbb{R}^d$, such as the Gaussian kernel $\exp(-\tfrac12\|x-y\|_2^2)$, using independent samples from its spectral measure to…A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering
Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother…nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds
Nearest-neighbor (NN) search underlies countless robotics algorithms, but many state spaces are not Euclidean: orientations live on $SO(2)$ or $SO(3)$ and poses on $SE(2)$ or $SE(3)$, and a…A Fast Greedy Algorithm with a 0.45 Approximation Guarantee for the Airplane Refueling Problem
We study a natural greedy algorithm for the Airplane Refueling Problem (ARP), based on a well-known priority rule.Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
We give a polynomial-time randomized classical algorithm that approximates the largest eigenvalue $λ_{\max}$ of a traceless quartic fermionic Hamiltonian $H$ on $n$ modes.Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
We study static indexes for exact subsequence matching over all equal-length windows of a time series.Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time
We give an $O_{d,\varepsilon}(n+N^{d+\varepsilon})$-time algorithm for multidimensional subset sum on an explicitly listed multiset of $n$ vectors in $[-N,N]^d$, for every fixed $d$ and…Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for…