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
Quadratic-Time Barriers from Self-Referential SAT
Under the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit distance on binary strings in…Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$.GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization
GreedTok (Lim, Tan, Choo and Lauw, NeurIPS 2025) builds a tokenizer vocabulary greedily for the partition-cover objective: choose $k$ tokens so as to maximize the number of adjacent character pairs…Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant
The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices…Constant-Factor Approximation Algorithms for Weighted Budgeted Multisensor Sweep Coverage
Sweep coverage requires each point of interest (PoI) to be revisited by some mobile sensor at least once during every sweep period, and it underlies persistent patrolling, environmental monitoring…A Simple Discrete Newton Method for the Quickest Transshipment Problem
The quickest transshipment problem is a problem defined in a dynamic network with multiple sources and multiple sinks.Sharp Limits of Graph-Based Nearest Neighbor Search on the Sphere
We study the degree needed for greedy graph search to find the exact nearest neighbor from every starting point on graphs of $n$ independent data points on the unit sphere in $\mathbb R^d$.Approximate Hamming Convolution via Rectangular Matrix Multiplication
We study $(1 \pm ε)$-approximate text-to-pattern Hamming distance: given a length-$N$ pattern and a length-$2N$ text, compute the Hamming distance at every alignment to relative error $ε$.Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering
We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd…Newton Steps are Faster for Linear Complementarity Problems
Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968).Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut
We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size.Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness
Dominant Resource Fairness (DRF) is an influential policy for sharing multiple resources among jobs with heterogeneous demands.Solving Linear Programs in the Matrix Multiplication Time
We give a randomized algorithm for feasible bounded-box linear programs with $n$ variables and $d\le n=O(d)$ linearly independent equality constraints.Sum-of-Squares Refutation Implies Planted Recovery for Semirandom CSPs
We give a $n^{O(\ell)}$-time algorithm for solving semirandom planted instances of a $k$-ary Boolean constraint satisfaction problem (CSP) with $m \gtrsim \left(\frac{n}{\ell}\right)^{k/2} \ell \…First-Order Model Checking on Monadically Dependent Graph Classes
Monadically dependent graph classes are those in which first-order logic cannot encode all graphs.Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism
Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations.Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum…Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection
The Minimum Bisection problem asks whether an $n$-vertex graph can be split into two halves with at most $k$ edges between them.All minimum cuts of symmetric submodular functions
We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time.Minimum-Cost $k$-Arborescence Packing in $\tilde O(km+k^4 n)$ Time
We give a deterministic, strongly polynomial algorithm running in $\tilde{O}(km+k^4n)$ time that finds $k$ arc-disjoint arborescences of minimum total cost in a directed multigraph with $n$ vertices…