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 22
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computation.Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space.Private Evaluation of High-Dimensional Functions
We study differentially private black-box evaluation of arbitrary high-dimensional functions.A Combinatorial $(1/2-\varepsilon)$-Approximation for $k$-Submodular Maximization under Multiple Knapsacks
We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2…Improved Space Bounds for Promise Graph Coloring in Adversarial Streams
We study promise graph coloring in one pass insertion-only adversarial streams.Tight weighted paging with delay via mirror descent
We give an O(log k)-competitive randomized algorithm for weighted paging with delay.Mean-only Prophet Inequalities
We study mean-based algorithms for single-choice prophet inequalities: the algorithm knows the number of variables and the mean of their maximum, but not their distributions.Simplified and Faster Algorithms for the Directed Single/Dual-Failure Replacement Paths via Modulo-Layer Hitting Sets
We study the replacement paths problem in unweighted directed graphs with $n$ vertices and $m$ edges under one or two edge failures.Enumerating Small Potential Maximal Cliques with Fixed-Parameter Delay
A potential maximal clique (PMC) of a graph $G$ is a nonempty vertex set that forms a maximal clique in some minimal triangulation of $G$.Navigable Graphs for Low-Dimensional Hyperbolic Spaces
A directed graph on a point set $P$ in a metric space $(X,d)$ is navigable if for every ordered pair of distinct points $s,t \in P$, $s$ has an out-neighbor $v$ with $d(v,t) < d(s,t)$, so greedy…Algorithms for Connected Multicuts of Weighted Trees
In the \emph{connected multicut problem for weighted trees}, the instance is an edge-weighted tree $T = (V,E,ω)$, a set of terminals $Γ\subseteq V$, and a set of pairwise ``conflicts'' between these…Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
We study quantization for inner-product estimation when storage and reading have separate budgets.Competitive Online Clustering with Movement Cost
We study the problem of online clustering with movement cost, which generalizes the fundamental $k$-server problem.On the Metric Distortion of the Minimum Spanning Tree Problem
We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices induced by these…Online geometric matching and segments block points
Given a sequence of online points in general position in the plane, the geometric matching problem asks to match as many points as possible, subject to segment crossing constraints.Critical-state algorithms for lot sizing with all-units discounts and variable inventory bounds
We study deterministic single-item lot sizing with all-units quantity discounts, linear holding costs, and time-varying end-of-period inventory bounds.Peak-Memory Schedules You Can Trust: Exact Realization, Certified Optimality, and the Limits of Recomputation for Inference
Real-time inference on small devices needs low activation memory without extra latency, which makes operator order the most valuable memory lever: it is free in time.Simpler Algorithms for Capacitated $k$-Median with $(1 + ε)$-Violations Using New Inequalities
We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+ε)$-cardinality or capacity violations.Power of Conditional Sampling on Hypergraphs
Let $G=(V,E)$ be a $d$-uniform hypergraph with $|V|=n$ and $|E|=m$.Deterministic Global Minimum Cut Using $\tilde{O}(n^{3/2})$ Cut Queries
Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model.