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 46
Tight Approximation Results for Matroid Optimization with a Linear Constraint
We study the following class of matroid optimization problems with a linear constraint (P-MOL).Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials
We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$…Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining.Improved Algorithms for the Remote Point Problem
The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far…Exponential Quantum Advantage in Testing Fourier Dimensionality
A boolean function $f$ has Fourier dimension $k$ if its nonzero Fourier coefficients span a subspace of dimension $k$.Structural Complexity of Matching-Match: Dense and Sparse Graphs
The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset.Sample-Based Prophet Inequalities for Random Walks
We study prophet inequalities for a random walk reward stopping problem with sample-based information.Factorisability of Low Dimensional Non-Negative Integer Matrices
We consider the problem of determining if a given two-dimensional nonnegative integer matrix $M$ is the product of two such matrices, excluding trivial units.Approximation Algorithm for the Min-Cost Bipartite Matching with Penalties
In this paper, we study the minimum-cost bipartite matching with penalties problem in metric spaces with bounded doubling dimension: Given two disjoint sets $R, B$ in a metric space $\mathcal{M}$…Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
Streaming principal component analysis (PCA) seeks to recover a leading spectral subspace in a single pass over a data stream.A $59/33$ Cut-LP Guarantee for Matching Augmentation
The Matching Augmentation Problem (MAP) asks for a minimum-cardinality set of unit-cost edges that, together with a zero-cost matching, forms a 2-edge-connected spanning multigraph.Pangenome Optimization via Elastic Degenerate Strings
An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets.Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness
In the unrestricted max--min metric $T$-join problem, one seeks an even terminal set $T$ maximizing the cost of a minimum $T$-join.Polylogarithmic Collective Tree Exploration
We study asynchronous collective tree exploration, where $k$ agents with unrestricted communication start at the root of an unknown tree and discover edges online.Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions.Fast Geometric Spanners via Approximate Nearest Neighbor Search
We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search.Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the…Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
In the chip testing problem, we are given $n$ chips, strictly more than half of which are good.Minimum Sum Vertex Cover via Minimum Vertex Cover
The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals
Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally.