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 53
Efficient Robust Learning at the Information-Theoretic Limit
In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the…A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
The $\textit{Colored Knapsack Problem}$ (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which…A 3.1462-Competitive Algorithm for Matroid Secretary
The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions.Structural Parameterizations for Eternal Vertex Cover
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$.A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
The demand matching problem generalizes both the knapsack problem and the $b$-matching problem.Critical and near-critical influence bounds for ferromagnetic Ising models
For a ferromagnetic Ising model on a graph of maximum degree $Δ\ge3$, we prove a bound of order $\sqrt n$ on every row of the influence matrix at the tree uniqueness threshold.A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics
We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric.Fast Stencil Computations on a Single Arbitrarily Moving Interval
A stencil computation repeatedly updates every cell of a grid from its neighbours' values at the previous timestep.Accelerated Local Algorithms for Personalized and Regularized PageRank
Local PageRank algorithms seek sparse approximations with work independent of graph size.The Complexity of Weak Partition Connectivity in Hedgegraphs
We prove that the integer-threshold decision problem for weak partition connectivity in hedgegraphs is NP-complete, answering an open question about its computational complexity.The threshold for online balancing of i.i.d. binary vectors
Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$.Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\ldots,A_n\in\mathbb{R}^{n\times n}$ with $\|A_i\|\le1$ there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$…Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna
We study the problem of fairly allocating m indivisible items among n agents with possibly unequal entitlements in the mixed manna setting, where each item may be perceived as a good or a chore by…A Deterministic $(2+\varepsilon)$-Approximation for Weighted Feedback Vertex Set in Tournaments
We study the weighted feedback vertex set problem in tournaments.A Faster Undirected Single-Source Shortest Path Algorithm
The single-source shortest paths (SSSP) problem in graphs with non-negative edge weights is one of the most classic problems in algorithms.Bandits with Probing: Optimal Regret and the Limits of Winner Feedback
A learner probes at most $k$ of $n$ arms each round, receives the maximum of their rewards in $[0,1]$, and competes with the best fixed arm.Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm
We revisit Valiant's algorithm (Commun.Single-Machine Scheduling with Interval Predictions and Costly Preemption
We study the single-machine total-completion-time problem $1||\sum C_j$ when processing times are unknown but each job comes with a reported interval.Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons
The Art Gallery Problem (AGP) asks for the fewest guards that see all of a simple polygon.Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research.