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 11
$\ell_{\infty}$ norm SVP in $\widetilde{O}(3^n)$
We give a classical randomized algorithm for the Shortest Vector Problem in the infinity norm in $\widetilde O(3^n)$ time and space, improving the previous bound of $2^{2.443n+o(n)}$.Differential Privacy for Generalized Entropy Indices of Income Inequality
The mean log deviation and the Theil index are two widely used measures of income inequality.Subexponential-Time Exact-One Hitting Set
Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in…Shared Randomness and Parallel Rounds in Permutation Sampling
We study the shared randomness needed to sample a uniform permutation in parallel output rounds.A smaller kernel for Ptolemaic Vertex Deletion
In the Ptolemaic Vertex Deletion problem, the input consists of an undirected graph $G$ and an integer $k$.The Value of Steiner Hubs in Two-Hop Distance Labeling
Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying…The Movement Complexity of Sorting
The complexity of sorting is usually measured by the number of comparisons.Fluid Limits and Upper Bounds for Randomized Greedy Matching
The Modified Randomized Greedy (MRG) algorithm [Tinhofer (1984), Aronson-Dyer-Frieze-Suen (1995)] is a classical greedy algorithm for finding approximate maximum matchings.How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed.A Numerical Refinement of an Exact Discrete Fourier Transform Bound
We refine the numerical bounds in Kartal's instantiation of Sussman's exact discrete Fourier transform construction.Reading between the levels: new tools for the Thorup-Zwick hierarchy and their applications
In this paper, we develop three new analytical tools for the Thorup-Zwick hierarchy: the Mixed-Level Growth, Two-Level Growth, and Long-Short Growth lemmas.A Decomposition Theorem and a Simple Algorithm for Contraction Fixed Points
We prove a decomposition theorem for the problem of computing an approximate fixed point of a contraction map $f\colon [0,1]^k \to [0,1]^k$ under the $\ell_{\infty}$-norm.Metric Testing: A Characterization of One-Sided Testability
We give a unified framework for one-sided testability (constant-query testing) of metric families.The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
A well-known conjecture in online algorithms is that the (randomized) competitive ratio of online budgeted allocation is $1-1/e$.Traveling Salesman Problem on Graphs with Proportional Independent Set
We give a deterministic algorithm for minimum-cost Hamiltonian cycle in undirected graphs with arbitrary real edge costs and an independent set of size at least $αn$, for any fixed $3/7<α\le1/2$.Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
We study \textsc{Capacitated Facility Location}, a fundamental clustering problem, in the setting of uniform opening costs and non-uniform capacities.Random-Sign IBLTs: Calibration-Free Self-Sizing After Decoding Failure
We propose the random-sign Invertible Bloom Lookup Table (IBLT) for calibration-free self-sizing after decoding failure.Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control
In periodic-review stochastic inventory control, replenishment policies must balance holding and backlogging costs while responding to uncertain demands and evolving forecasts that may be…New bounds for online coloring three-colorable graphs
We prove new lower and upper bounds for online coloring of three-colorable graphs, improving classical bounds of Vishwanathan [FOCS'1990] that have stood for more than three decades.Steiner Tree Parameterized by Multiway Cut: Single-Exponential Time and Polynomial Space
In the Steiner Tree problem, the goal is to find a minimum-weight tree containing a given set of terminals in an edge-weighted graph.