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 32
The Multiple Unicast Conjecture is False
The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow.Attention via Black-Box Vector Search
Sparse attention mechanisms estimate attention over $n$ tokens using a small subset of keys.3SUM Is Really Hard: A Real-to-Integer Reduction
We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs.On the Cyclic Assumption of the Cow-Path Search Algorithm
In the cow-path problem, a cow must find a goal lying at an unknown distance on one of $w$ paths connected only at the origin, and performance is measured by competitive ratio.Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering
We present a deterministic reduction from min-sum subset convolution to min-plus matrix product.Polynomial Kernels for Interval Completion
An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval graph by adding at…Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem
Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional lower bounds for fundamental…Settling the Sample Complexity of Rényi Entropy Estimation
Rényi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans.Color Coding for the Sherrington-Kirkpatrick Model
We give a polynomial-time algorithm for approximating the partition function of mean-field mixed $p$-spin models to arbitrarily high accuracy throughout the second-moment regime.Subset Sum via Partial Match
We show that the subset sum problem can be solved in time $O(2^{0.499999n})$, breaking the $2^{n/2}$ meet-in-the-middle barrier.Fast Almost-Uniform Sampling of Random $k$-SAT Solutions
We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas.Rectangular matrix multiplication from polynomial products
In this note, we extend the matrix-multiplication analysis by OpenAI to rectangular products and prove $ω(1,k,1)\le2$ for $0\le k\le\frac{1}{2}$, and $ω(1,k,1)\le1+k+\frac{1}{4k}$ for…Taxonomic Classification with Tag Arrays
Taxonomic classifiers based on exact matches differ in which matches they use and in how each match splits its credit among the taxa containing it: Kraken~2 gives a $k$-mer's credit to the lowest…Barely Monotone (min,+)-Convolution in Truly Subquadratic Time
The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]).Symmetric Submodular Minimization from Comparisons
Given value-oracle access to a symmetric submodular function $f:2^V\to\mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries.Deterministic Distance Selection in $O(n^{4/3})$ Time
Let $P$ be a set of $n$ points in the plane.Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$)
Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$-outerplanar graphs can be embedded into trees and $\ell_1$ with distortion $2^{O(k)}$.Directed Global Minimum Cut in Almost-Linear Time
We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$.$Ω((\log n/\log\log n)^2)$ Lower Bounds for Dynamic Graph Problems
We prove an $Ω((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed…Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
String attractors provide a compact way of representing the complete factor structure of a word: a set of positions is an attractor if every distinct factor has at least one occurrence crossing one…