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 12
List 3-Coloring in tame classes of graphs in quasipolynomial time
A class of graphs $\mathcal{G}$ is tame if there is a constant c such that every $n$-vertex graph in $\mathcal{G}$ has at most $n^c$ minimal separators.Lowered crossover points of Anthropic's subexponential 3-SAT algorithm
The October 2026 refutations of the Exponential Time Hypothesis count satisfying assignments in time $2^{o(n)}$, but an asymptotic bound does not say from which input size, the crossover point, they…A Better Lower Bound for Sublinear Metric Steiner Tree
In the metric Steiner tree problem, we are given an $n$-point metric space $(V,w)$ and a set of terminals $T\subseteq V$, and we are interested in the smallest total weight $\mathsf{st}(V,T,w)$ of a…A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability
We give a fully polynomial randomized approximation scheme for all-terminal unreliability in explicitly represented undirected hypergraphs of arbitrary rank.Catalytic space-efficient algorithms for Distance and Determinant
Catalytic computation reuses potentially large but in-use space (or catalytic space) which must be restored to its initial contents while the clean space is small.Degree Realization with Maximum Matching
The Maximum Matching Degree Realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph(whose degree sequence corresponds to $d$) with the maximum…Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs
The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||\sum_jw_jU_j$) asks for a schedule of jobs each with a processing time, weight, and due date on a constant number…Revisiting the directed pathwidth of h-semicomplete digraphs
A digraph is $h$-semicomplete if every vertex has at most $h$ non-neighbors.Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
We show that any $n$-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most $O\left(\sqrt{\frac{\log n}{\log\log n}}\right)$, matching a known lower…The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth
We give approximate counting and sampling algorithms for spin models on graphs of low threshold rank or high girth.3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized
Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and…Optimal Online Weighted Connectivity Augmentation
In the online Weighted Connectivity Augmentation Problem (WCAP), we are given a $k$-edge-connected graph on $n$ vertices and a set of additional edges, called links, with nonnegative costs.Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$
Given a simple undirected graph on $n$ vertices, random $k$-out sampling forms a spanning subgraph by having each vertex independently choose $k$ incident edges uniformly with replacement.The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight
Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems.Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications
Let $P$ be a simple polygon with $m$ vertices.Differentially Private Synthetic Data from Sliced Chebyshev Moments
Research on practical differentially private (DP) synthetic data has largely focused on methods that approximately preserve low-dimensional marginals of a target distribution, and can thus only hope…The Pareto Secretary Problem
The Pareto secretary problem asks for online selection of a Pareto-maximal observation from an i.i.d. sample: no other observation is at least as good in every coordinate and strictly better in one.FastHeapDict: Permanent Slot Indexing for Efficient Decrease-Key Operations in Indexed Priority Queues
Efficient decrease-key support remains an important practical concern in priority queues used by shortest-path and graph-processing algorithms.Online carpooling against an oblivious adversary
In the online carpooling problem, edges on $n$ vertices arrive one at a time and must be oriented immediately, so as to keep the difference between the indegree and the outdegree of every vertex…Max Weight Independent Set in graphs with no long claws nor large induced bicliques
The complexity of Max Weight Independent Set (MWIS) in graphs excluding a fixed subdivided claw is one of the central open problems in algorithmic graph theory.