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 2
Connectivity in a New Bounded-Space Dynamic Model
We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace.A Near-Optimal Generalized Sorting Algorithm
We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting.Low-Temperature Sampling via Equilibrium Disagreements
We develop a new framework for sampling at low temperatures using Glauber dynamics.Tusnády's problem and online two-sample thinning
We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension $d\ge 2$.Canonical Cut Hierarchy in Almost-Linear Time via Reduction to Max-Flow
The canonical cut hierarchy recursively partitions a graph along Tutte-Nash-Williams partitions, choosing the partition with the most number of parts at each step.Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Online optimization with delays has emerged as a powerful paradigm with numerous applica- tions, including matching, caching, server management, network design, and set cover.Sublinear Metric Distortion for Matching
We study metric distortion in one-sided matching.Near linear mixing of random-cluster Glauber dynamics on random regular graphs
We study the random-cluster model on locally treelike graphs at low temperatures.Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
We study the component-oracle complexity of finding approximate local minima of nonconvex finite sums under mean-squared averaged smoothness with parameter $L$ and a $ρ$-Lipschitz average Hessian.Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
We study the query complexity of sampling from smooth distributions on $\mathbb R^d$ using first-order oracles.Makespan Bounds for Synchronous Pebble Motion on Graphs
We study the largest minimum makespan of labeled pebble motion on graphs under a model that permits synchronous pebble movement.Improved Bounds on Distance Preservers
Given an undirected unweighted graph $G$ on $n$ vertices and a set $P$ of $p$ pairs of its vertices, a distance preserver is a sparse subgraph of $G$ that exactly preserves the shortest-path…Improved approximation algorithms for capacitated cluster editing
We study the minimum-disagreement cluster editing problem that, from a complete edge-signed graph, where a positive edge represents two vertices agreeing to each other while a negative represents a…Faster Isomorphism for Groups of Class 2
The finite-group isomorphism problem asks whether two groups, given by their Cayley tables, are isomorphic.Faster Dynamic Maximal Independent Set against Adaptive Adversaries
We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on $n$ vertices with at most $m$ edges under edge insertions and deletions.Single-Variable Connectivity in Random $k$-SAT
We resolve longstanding questions about connectivity, reconstruction,and looseness in random $k$-SAT, for sufficiently large fixed $k$ as the number $n$ of variables tends to infinity…Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition
Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts.Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee
Partitioning the vertex set of a graph $G=(V,E)$ into clusters is a classical problem in computer science.Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^{O(1/\varepsilon)}$ Queries
A local computation algorithm (LCA) for matching answers ``who is the mate of $v$?'' by inspecting only a small part of the graph, with all answers consistent with one matching.Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds
Attention is central to modern AI models for language, vision, and scientific modeling.