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 33
Non-Clairvoyant Scheduling is Hard Even for Trees
We study online scheduling of parallel jobs on $m$ identical processors to minimize maximum flow time.Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction
The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem.Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Probability forecasts are calibrated when predicted probabilities match empirical outcome frequencies: among events assigned a probability $p$, we'd hope that the fraction of positive outcomes is…How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric.When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Byzantine quorum safety relies on correct replicas refusing to sign conflicting values.Almost Instance Optimal Sum and Moment Estimation Using Weighted Sampling
We design an almost instance optimal algorithm for the sum estimation problem using weighted sampling.Efficient Posterior Sampling for $\mathbb Z_2$ Synchronization
Consider the $\mathbb Z_2$ synchronization problem \[ \boldsymbol{Y} = \fracλ{\sqrt n} θθ^{\top} + \boldsymbol{Z}, \] where $θ$ is uniform on $\{-1,1\}^n$ and $\boldsymbol{Z}$ is an independent…A Fast Algorithm for Maltsev Constraints
The constraint satisfaction problem over a set of relations $Γ$ (CSP($Γ$)) is the computational problem of deciding if a set of constraints admits at least one solution.Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
We study isomorphism decision and basis construction for finite Abelian groups of known order $n$.Faster dynamic programming for tridiagonal maximum-entropy sampling
The maximum-entropy sampling problem (MESP) seeks, for an order-$n$ covariance matrix $C$, a principal submatrix of order $s$ with maximum log-determinant.Explicit tensors beyond the linear flattening barrier
We construct explicit n x n x n tensors of border rank at least 3n-o(n), improving the previous record of (2 + $\varepsilon$)n due to (Landsberg and Michalek 2025).Finite-Precision Gram-Schmidt Walks
The Gram-Schmidt Walk is a randomized vector-balancing algorithm whose subgaussian guarantees support applications in discrepancy, experimental design, and data compression; however, these…Parametrized Exact Hardware-Software Partitioning
When optimizing computing architecture for specific computationally intensive tasks, such as evaluating or training a neural network, it is important to identify what computational subtasks will…Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
We prove that the probability that Gaussian elimination with partial pivoting on $n \times n$ random matrices has growth $ρ$ is at least inverse quasi-polynomial: $Ω(\exp(-c \log^2 (ρ)\log(n)))$ for…Optimal and Efficient Online Inverse Optimization
In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on $\mathbb{R}^{d}$; the goal is to…Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
Let f:2^N --> \cZ^+ be a polymatroid (an integer-valued non-decreasing submodular set function with f(emptyset) = 0).Efficient Algorithms for Online Subadditive Combinatorial Allocations
For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a $6$-competitive online algorithm, improving on the previous best…On the complexity of the single-move labeled token routing problem
In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom.Massively Parallel Algorithms for Huffman Coding
Huffman coding is one of the oldest and most fundamental problems in computer science.Lower Bounds for Parallel Diffusion Sampling
Standard diffusion samplers generate samples through repeated evaluations of a learned score function.