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 49
A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees
Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_iA_i=I$ and $\|A_i\|\le\varepsilon$.The Cube-Root Phenomenon in Online Carpooling
We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at each vertex small.Faster SVP in Polynomial Space
Kannan's algorithm, as analyzed by Hanrot and Stehlé in 2007, solves the exact Euclidean shortest vector problem in polynomial space and $n^{\frac{n}{2e}+o(n)}$ time.Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases
Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function $f\colon 2^E \rightarrow \mathbb{R}_+$ over maximum cardinality…Fair Prophets
We initiate the study of $α$-fair prophet inequalities.Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance?Sampling Matchings in Near-linear Time
For every fixed activity $λ>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $Δ$.Dynamic Contention Resolution Schemes
We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs).A lower bound for $\langle 3,2,m \rangle$ matrix multiplication
We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$.The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration
An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace.When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance
Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry.Hardness of Online Directed Steiner Network
In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair.Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders.Universal set families for maximization of nonnegative submodular and XOS functions
We consider the question of designing a universal family of sets $F \subset 2^{[n]}$ such that for any function $f:2^{[n]} \to R_{\geq 0}$ in a certain class, we have $$\max_{S \in F} f(S) \geq c(n)…A $(1+1/\sqrt{2})$-Approximation for the Multiple-Depot Traveling Salesman Problem
The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost tour covering all clients in a metric graph.Almost Optimal FPT Inapproximability for k-SetCover
We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH.Improved Algorithms for Beck--Fiala with Bounded Sets
We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size.A Refined Analysis of the Sequential Access Theorem for Splay Trees
A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized $O(\log n)$ time, where $n$ is the number of stored elements.Polynomial Time Algorithms for the Kadison-Singer Problem
Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions.ZigZag Trie: A Novel Index for Contextual Queries
There is increasing interest in queries about the context of a string $P$ in a longer text $T$, i.e., the set of all string pairs $(L,R)$, with $|L|=|R|=q$, for a given $q$, such that the string…