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 16
Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
Local-to-Global theorems are a cornerstone of many of recent developments in theoretical computer science from coding theory and PCPs all the way to analyzing mixing time of Markov chains.Generating pivot Gray codes for spanning arborescences of complete digraphs and split digraphs in constant amortized time
We present the first known efficient algorithm to generate pivot Gray codes for spanning arborescences of complete digraphs, listing all spanning arborescences such that consecutive arborescences…A Simple Optimistic B-Skiplist Algorithm
We present the first optimistic concurrent B-skiplist, built on optimistic lock coupling (OLC).Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization
We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines.The Complexity of Value Optimization in Sporadic Task Systems
Value-based Task Selection (VTS) asks whether a real-time system can select tasks whose total value reaches a required target while preserving every deadline.Linear Hashing Is Poissonesque
The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent…When is greedy exact for weighted minimum 3-cut?
The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight $4/3$-approximation.Order-selection Prophet Inequality (Almost) Goes I.I.D
We study the order-selection prophet inequality.Attention under Bounded Key-Query Similarity: Space Complexity and Transformer Anisotropy
A growing body of work on KV-cache compression aims to reduce the memory requirements of autoregressive generation.From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids
We study the problem of submodular maximization under a matroid constraint.Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set
We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem.Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra
Large sparse matrices---adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases---are routinely compressed to save space.Query Complexity of Learning Axis-Aligned Partitions
This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting.Tiny Suffix Arrays
Suffix array and inverse suffix array queries on a text of length $n$ can be answered in $\widetilde{O}(τ^3)$ time using an auxiliary data structure occupying $O(n/τ)$ words, for any $τ\in [1,n]$.An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs
We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors.A Nearly Optimal Min-Cut Algorithm for Dynamic Streams
We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors.Bicriteria Approximate Navigable Graphs in General Metrics
We study approximation algorithms for constructing sparse navigable graphs in general metrics.Tight Coreset Bounds for Euclidean $(k,z)$-Clustering
We study the optimal coreset size for Euclidean $(k,z)$-clustering, where $z\ge1$ is fixed.Online Discrepancy of Sparse Random Vectors over Long Horizons
We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of $s$ of the $n$ coordinates, with nonzero entries equal to one (binary…Unconditional Lower Bounds for the Fredman--Khachiyan Algorithms for Monotone Boolean Duality Testing
We prove unconditional lower bounds on the number of recursive calls made by the two algorithms of Fredman and Khachiyan (1996) for monotone Boolean duality testing, as a function of the explicit…