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 4
Generalized Sorting via Four-Cycles
We study the generalized sorting problem where only a subset of the pairs can be compared.A Quantum Lower Bound for Triangle Finding
Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques.Approximation and Hardness for the Data Validation Problem
Finnah, Gönsch and Otto [Eur.Finding full immersions is fixed-parameter tractable in labeled tour graphs
We give an $O_H(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $H$.Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic.The 3-Uniform Hyperclique Hypothesis is False
We present truly subquartic algorithms for detecting or counting 4-hypercliques in a 3-uniform hypergraph with $n$ vertices, disproving a popular hypothesis in fine-grained complexity.Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space
A fault-tolerant (FT) connectivity oracle for an $n$-vertex graph $G=(V,E)$ determines whether $G- F$ is connected for any query set $F\subseteq E$.Prophet Secretary for Matroids and XOS Valuations: A Strict Separation at $1-1/e$
The matroid prophet-secretary problem asks an online algorithm to select an independent set of elements whose nonnegative values are drawn independently and revealed in uniformly random order.Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap
In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network…Online Edge-Weighted Matching Beyond 0.55
We give a $0.556195$-competitive randomized algorithm for edge-weighted online bipartite matching with free disposal, improving the $0.5368$ guarantee of Blanc and Charikar.A Simple Subquadratic Cut Query Protocol for Directed Reachability
We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$…Resolving Tusnády's Problem
We prove a lower bound of $Ω_d((\log N)^{d-1/2})$ for the worst-case combinatorial discrepancy of $N$-point sets with respect to anchored boxes in every fixed dimension $d\ge3$.Polynomial Lower Bounds for Steiner Shortcuts via Test Functions
The Steiner shortcut problem asks whether every directed graph $G=(V,E)$ with $n$ vertices and $m$ edges admits an augmentation $G_{+}=(V\cup V_{+},E\cup E_{+})$ with $m^{1+o(1)}$ edges such that…Stacking Stars: Minimum-Area Packing with and without Rotation
We study the problem of packing a given set of polygons into a minimum-area convex container, that is, placing them without overlap so as to minimize the area of their convex hull.$L_1$ versus $L_2$ Clustering: When Does the Choice of Norm Matter?
We study how well approximation guarantees for clustering under one norm translate into guarantees under another.A Constant-Factor Approximation for Capacitated Facility Location with Outliers
We give a deterministic polynomial-time $(60/11+\eps)$-approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities.Semidirect sums of tensors and the matrix multiplication exponent
This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent.Incremental Open Addressing Has No Time-Space Tradeoff
In this paper, we show that there is no time-space tradeoff in incremental open addressing: there is an incremental open-addressed hash table that supports $O(1)$ worst-case expected time…Online Metric Matching with Unknown i.i.d. Arrivals
We study online metric matching with $n$ servers and $n$ requests drawn independently from an unknown distribution.Testing Implies Distance Estimation with Polynomial Loss
A tester decides whether a graph has a property or is far from having it.