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 42
Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems
The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian…Competitive Random-Order Correlation k-Clustering
Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications.Learning sparse quantum states from single-qubit measurements
We study the problem of learning a sparse quantum state, an $n$-qubit quantum state whose density matrix has at most $s$ nonzero matrix entries in an unknown product basis.Optimal Query Complexity for Ground-State Preparation
We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known.More Efficient Parallel $(Δ+1)$-Edge Coloring
This paper gives two parallel algorithms for $Δ+1$ edge coloring, where $Δ$ denotes the maximum degree of any vertex.Near-Optimal Bounds for Testing Residual-String Equality and Parenthesis Languages
Residual-String Equality, denoted $\texttt{ResStringEq}$, is the property consisting of all pairs of strings over $\{0,1,*\}$ that are equal after deleting all `$*$' symbols from them.Approximating the Chvátal--Gomory Closure of Capacity-Bounded Min-Closed Systems
Optimizing over the {0, 1/2} rank-1 Chvàtal-Gomory (CG) closure of a binary integer linear program is NP-hard.Maximizing Social Influence in Almost Linear Time
Influence maximization is a central algorithmic challenge in network analysis, aiming to identify a set of $k$ seed nodes in a graph with $n$ nodes and $m$ edges that maximizes the expected cascade…Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching
In this work we initiate the study of competitive algorithms with arrival-time incentive compatibility for random-order online bipartite matching in settings where the users care only about…Distance flexibility in spatial matching: the value of concentration
In spatial matching markets, a supply unit's flexibility is measured by its service radius, the maximum distance at which it can serve demand.Dual lattice attacks for bounded distance decoding, revisited
Analyses of dual lattice attacks have often assumed that the individual scores associated with short dual vectors are mutually independent.A Tight Second-Order Lower Bound for Routing Labels in Trees
In the designer-port routing-labeling problem, every vertex of a rooted tree receives a binary label and the child edges receive distinct port numbers.On Diverse Solutions to Max-k-CSP and Bounded Degree k-SAT
We study the problem of generating diverse solutions to Max-$k$-CSP and bounded-degree $k$-SAT, focusing on two distinct metrics: constraint diversity and variable diversity.On the Guo-Fang-Lu Algorithm for Komlos Discrepancy
We give an exposition of the recent polynomial time algorithm of Guo, Fang, and Lu for the Komlos problem.On the Complexity of Forcing and Anti-Forcing Minimum Cuts
For an instance of a combinatorial optimization problem, a \emph{forcing set} is a set of elements such that there is a unique optimal solution including it.Geometry-Adaptive Mechanisms for Private Synthetic Data
Generating differentially private synthetic data with meaningful Wasserstein utility guarantees is challenging in high dimensions.An EPTAS for Offline Temporary Tasks Assignment on Few Machines
In offline temporary tasks assignment, each job has a time interval and a positive weight and is assigned to one of $r$ identical machines for its entire interval; the goal is to minimize the peak…Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates
We give a randomized polynomial-time algorithm that, for every fixed $\varepsilon > 0$, colors every $3$-colorable $n$-vertex graph using $O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx…Solving Vertex Integrity Faster than $2^n$
Vertex Integrity is a classical graph parameter measuring the vulnerability of a network to vertex failures.Tight Efficiency Guarantees for Strategyproof Linear Regression
We study the trade-off between squared-error accuracy and incentive compatibility in linear regression.