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 51
Learning Depth-3 Circuits with Polynomial Savings
We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning.Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection
Let $\mathcal{M}_1,\mathcal{M}_2$ be two matroids on a common ground set $V$, given by independence oracles, and let $S$ be a maximum-cardinality common independent set.Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents
The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns.The Complexity of Undirected Partizan Edge Geography
Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge.NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance
In this paper we study the genome rearrangements done by translocation events.Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch
We consider the problem of estimating the trace of an implicit matrix $\mathbf{A} \in \mathbb{R}^{d^p\times d^p}$ that can only be accessed through matrix-vector products queries.Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set
We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting.Total Variation Distance Estimation through Domain Reduction
Computing the total variation (TV) distance between succinctly represented high-dimensional distributions is generally intractable.A sampling Lovász Local Lemma
We give an approximately uniform sampler for satisfying assignments of constraint satisfaction problems that satisfy $4\mathrm e p(Δ+1)^2\le1$, where $p$ is the largest constraint-violation…A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$
We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$.Query-Optimal and Gate-Efficient Lindbladian Simulation
We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert…Routing Multiple Agents Below the Sum of Distances
We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to…Optimizing Both Checking and Update Costs in Random Walk Search
Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked.Degree-Free Spectral Independence for Log-Concave Holant Measures
We establish a degree-independent bound on spectral independence for log-concave Holant problems on simple graphs.A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture .A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer
The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the…A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams
We study the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model.On the Strong Matroid Secretary Conjecture and Beyond
The strong matroid secretary conjecture asserts that every matroid admits a $1/e$-competitive secretary algorithm, matching the classical single-choice guarantee.A $2$-Approximation for Directed Feedback Vertex Set in Locally Semicomplete and Quasi-Transitive Digraphs
A \emph{directed feedback vertex set} of a digraph is a set of vertices whose removal destroys all directed cycles.Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using $\tilde{O}(n^{2/3})$ space
The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(α+2)$-approximation for the size of the maximum matching in a graph of arboricity at…