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 9
Approximating Submodular Orienteering via Rooted Subgraph Decomposition
The Submodular Orienteering problem asks for an $s$-$t$ walk in a directed graph that maximizes a monotone submodular function over the visited vertices subject to a bound on its length.Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family $G$; that is, its residuals should be uncorrelated with every test…Stochastic Matching with Polynomial Degree
We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$.Online Algorithms Cannot Find Isolated Perceptron Solutions
The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\lfloor αn\rfloor$-many independent random Gaussian half-spaces.Expander Routing under Adversarial Deletions via Temporal Aggregation
In expander routing, we seek to establish paths in the expander graph between given source-target pairs while minimizing both dilation (maximum path length) and congestion (maximum edge load).The Optimizer's Windfall: Bounding Hindsight Gain under Random Restrictions
Suppose an optimization problem is randomly restricted, independently on each variable, and re-optimized after the restriction is revealed.Exact Sum-of-Radii Clustering under Any Constant Stability
We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives.Square-Root Pass Semi-Streaming Algorithms for Digraph Problems
We study directed graph problems in the semi-streaming model where we are restricted to $\widetilde{O}(n):=O(n\cdot \text{polylog}(n))$ space for processing the edge stream of an $n$-node graph and…Online Matching with Arbitrary Stochastic Rewards
Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability.Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing
In this paper, we study when two parties should pool their data to train a machine learning model.Near-Optimal Space and Time Cut Sparsification in Turnstile Streams
A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements.A GPU Engine for Sparse Matrix-Vector Products on $k^2$-Tree-Compressed Graphs
The $k^2$-tree is a compact representation of Boolean matrices: it stores the recursive hierarchy of their non-empty submatrices, with neither values nor coordinates, and serves rows and columns…Adjacency Labeling Schemes of Size $\log n+O(\log\log^* n)$ for Graphs of Bounded Treewidth
Gavoille and Labourel (ESA 2007) gave an adjacency labeling scheme of size $\log n+O(k\log\log n)$ for graphs of treewidth at most $k$, and asked whether $\log n+O(k)$ bits suffice.Get Permanent Results Faster by Counting Stars
We show that $n \times n$ permanents can be computed with $O^*{(2-\varepsilon)^n}$ arithmetic operations over every commutative ring, for $\varepsilon = 10^{-40}$.A King for Almost Everyone
A tournament is an orientation of a complete graph.A Family of Well-Behaved Multiflow Instances
We introduce a family of cut-sufficient instances for undirected multiflow that generalizes single-source planar and fully-planar instances.The Hyperclique Hypothesis is False
The Hyperclique Hypothesis postulates that, for all constants $k > h \geq 3$, detecting a $k$-clique in an $h$-uniform hypergraph with $n$ vertices requires time $n^{k-o(1)}$.On the optimality of truncation among binary linear sketches
We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity measurements.An $\mathsf{FPRAS}$ for Mixed Volumes
We design the first fully polynomial-time randomized approximation scheme ($\mathsf{FPRAS}$) to estimate the mixed volume of $n$ arbitrary compact convex sets in $\mathbb{R}^{n}$ specified by weak…Sharper Bounds for Graphical Two-Choice Allocation
In graphical two-choice allocation, vertices are bins, and each arriving ball must be placed irrevocably at one endpoint of a uniformly random edge.