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 18
Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
We study the fundamental problem of PAC learning positive linear combinations of $k$ arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$ loss.Acyclic 2-edge-coloured graphs: polynomial-time linkages and colouring hardness
A path or cycle in a $2$-edge-coloured graph is alternating if consecutive edges have different colours.Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing
In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to $1 - \varepsilon$ (for some parameter $\varepsilon \in (0, 1)$), while supporting…Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework
The subgraph isomorphism problem (SGI) asks a deceptively simple question: is a graph B found inside a parent graph A?Optimal Mixing for Local Edge-Coloring Dynamics on Trees
We study the mixing time of two local Markov chains for uniformly sampling proper edge colorings of trees.Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
Phylogenetic distance deconvolution represents mixture-to-reference distances by weighted sources placed on a reference tree.Near-Quadratic Time Multivariate Polynomial Interpolation
Let $\F$ be a finite field.Truthful by Omission: Click Thinning for LLM-Native Advertising
Generative AI assistants are becoming an advertising medium, embedding sponsored content in their answers.Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis
The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum.Almost tight distributed approximation for domination in sparse graph classes
We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion.Iterative Randomized Rounding for Better-Than-2 k-Median Approximation
We study the classic $k$-median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsilon)$-approximation.A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding
A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices.Kempe Reachability with $k\geq 3$ Colors Is $\mathsf{PSPACE}$-Complete on Claw-Free Graphs
A \emph{proper vertex coloring} assigns colors to vertices so that adjacent vertices have distinct colors.Hardness and Approximation for Compressing Deterministic Finite Automata
The delayed deterministic finite automaton ($\text{D}^2\text{FA}$) is a powerful tool for compressing the prohibitively large deterministic finite automata (DFAs) used in modern signature-based deep…A Sharp Analysis of Fixed Offset Hash Tables
We consider the class of open addressing hash tables that uses a fixed offset sequence $r_0,r_1,\ldots,r_{n-1}$ to find an open slot in the table.Pipelining vs. Combining in Aggregation Tasks
We study the aggregation task (convergecast) in networks in the case that the values to be aggregated do not fit in a single message.Peak-Aware One-Way Trading: Competitive and Learning-Augmented Algorithms for Energy Procurement
We introduce peak-aware one-way trading ($\texttt{PA-OWT}$), an online problem in which a player must purchase a fixed quantity of an asset by a deadline, minimizing its total cost plus a charge…Coresets for $k$-Means: When Does Uniform Sampling Suffice?
Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets.Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
We prove the all-exp property for the Traveling Salesman Problem with the $2$-opt neighborhood, and for $(3,2,2)$- and $(2,3,2)$-Maximum Constraint Assignment with the flip neighborhood.Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
We study learning a discrete distribution under person-level differential privacy in the batched setting.