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 6
Optimal Approximation for Constrained Correlation Clustering via Repulsion
The best-known approximation factor for constrained correlation clustering stood at three for nearly two decades, until a recent improvement to below $16/7$.Near-linear-Time Sampling of the Ferromagnetic Ising Model at the Tree Uniqueness Threshold
We give a near-linear-time sampler for the zero-field ferromagnetic Ising model throughout the tree-uniqueness regime, including the threshold itself.Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation
We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only translations.Real-to-Integer Reduction for All-Pairs Shortest Paths
Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems.Faster Regular Expression Matching via Two-Dimensional Tabulation
Regular expression matching asks whether a string of length $n$ belongs to the language described by a regular expression of length $m$.Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals
We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound…NP-Hardness and a PTAS for Maximum Interval Multicover, with Applications to Dense Subgraphs
Given intervals and points on a line, each point with a demand, and a budget $K$, Maximum Interval Multicover asks for at most $K$ intervals that satisfy as many points as possible, a point being…Local Distributed Computation under Crash Failures
We study deterministic algorithms for locally checkable graph problems in the synchronous LOCAL model with crash failures, where a crashing node may send messages to only some neighbors.The Power of Bidegeneracy for Hypergraph Data Structures
A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$.Near-Linear Lower Bounds for Testing Directed Acyclicity
We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors.Sorting in PRAM, Parallel Comparison Model and Parallel External Memory Model
We study the problem of sorting on the Parallel Random Access Machine (PRAM), Parallel Comparison Model (PCM) and Parallel External Memory Model (PEM).Metric Facility Location under Batched Random Order
We study online metric facility location in the batched random-order model.Faster Planar Diameter using Pseudoline Envelopes
We give an improved algorithm for weighted directed planar diameter that runs in $\widetilde{O}(n^{3/2})$ time.Nearly-Linear Query Algorithm for Submodular Maximization subject to a Matroid Constraint
We consider monotone submodular maximization subject to a matroid constraint.Matchings under One-Sided Preferences with Soft Quotas
Assigning applicants to posts in the presence of applicant preferences and quotas associated with posts is extensively investigated.The Power of Interaction in Locally Edge-Private Subgraph Counting
We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP).A Low-Diameter Nash-Williams--Tutte Theorem
The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition.Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes
In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space.Finding Hypercliques Faster Than Brute Force
We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in…Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs
We give an algorithm for PAC learning intersections of $k$ degree-2 polynomial threshold functions over $R^d$ under a Gaussian distribution.