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 21
Constructive Arithmetic Regularity for Abelian Groups
The arithmetic regularity lemma of Green is a fundamental tool in additive combinatorics, providing a decomposition of arbitrary subsets of finite Abelian groups into pseudorandom pieces with…Orienting mixed graphs for reachability pairs: When the all pairs setting is easier than the general one
Given a mixed graph $G$ and an ordered pair $(u,v)$ of vertices in $V(G)$, we say that an orientation $\vec{G}$ of $G$ satisfies $(u,v)$ if $v$ is reachable from $u$ in $\vec{G}$.Capacitated Line Aggregation with Maximum Delay
We study capacitated line aggregation with per-batch maximum delay.A Tight Oracle Threshold for \(k\)-Submodular Maximization
We prove that, for every \(\varepsilon>0\), a \((\frac{k}{2k-1}+\varepsilon)\)-approximation algorithm for maximizing monotone \(k\)-submodular functions requires exponentially many value-oracle…A simplified proof of the FPRAS for counting perfect matchings
We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs.A Short Note on Algorithms For The Noisy $k$-XOR Problem
This mostly expository note studies the sample-noise regimes in which the testing problem for noisy $k$-XOR in dimension $n$ can be efficiently solved.Deterministic Shift Equivalence Testing for Sparse Polynomials
We study the shift equivalence testing problem for high-degree sparse multivariate polynomials.Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs
We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints.Parameterizing Cluster Editing by the Number of Deletions
In Cluster Editing, we are given a graph $G$ and an integer $k$ and ask whether at most $k$ edge insertions and deletions turn $G$ into a disjoint union of cliques.Communication Complexity of Universal Features
Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions.No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches
Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection.Approximating Independent Sets Using Additive Combinatorics
We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph.Strategy recovery for Mean-Payoff Games is as hard as solving them from scratch
Mean-Payoff Games (MPGs) form an interesting family of deterministic, infinite-duration, zero-sum, turn-based games played by two players on a finite weighted directed graph.Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime
The class $\mathsf{PPP}$ captures fundamental total search problems, for which a solution is guaranteed to exist by the pigeonhole principle and the main challenge is to find it.Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
We study the mixing time of the single-site Glauber dynamics for sampling proper \(q\)-colorings on sparse Erdős-Rényi random graphs \(\mathcal{G}(n, d/n)\).A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$ time, where $\mathsf{EO}$ is the running time of a…Range Queries for Permutation Pattern Matching: Separations, Equivalences, and Applications
The problem of Permutation Pattern Matching (PPM) asks, given a permutation $π:[n]\to[n]$, viewed as the point set $P=\{(i,π(i)):i\in[n]\}$, and a pattern $σ$ of small length $k$, whether $P$…Degree Stability of Parallel Greedy Matching in Random Graphs
We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics.Searching subgraphs
We consider graph search models, in which an invisible, omniscient and fast intruder can hide anywhere in the graph, and the goal is to design a \emph{search strategy} composed of a sequence of…Near-Linear Time Maximum Clique in Circular Arc Graphs
We present a near-linear time algorithm to find a maximum clique in circular arc graphs, the intersection graphs of arcs on the circumference of a circle, answering a 30-year-old open question posed…