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 41
Query Complexity of Testing Structured Parenthesis Languages
We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations.Byzantine Causal Reliable Broadcast with Constant Metadata Overhead
Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees.Vanishing Ideals and the Computational Tractability of Sum-of-Squares over Boolean Domains
Building on the bit-complexity framework of Raghavendra-Weitz and the moment-SOS criteria of Gribling-Polak-Slot, we study the effective use of truncated vanishing identities over Boolean polynomial…Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs?A Tale of Two Walks: Kipnis, Marchioro and Presutti Meet Kac in a Quantum World
We reveal an unexpected connection between the parallel Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process.Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations
We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual…Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs
A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs).Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models
We present a deterministic CRT-based sparse Fourier architecture for exact recovery of noiseless, on-grid, at-most-\(k\)-sparse spectra with an engineered transform length.Online Stochastic Allocation with Increasing Returns
Online resource allocation is a fundamental problem in revenue management, sponsored search, and platform operations.Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation
In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval.Rounding the Ball LP for Fair Max-Min Diversification
Given $n$ points in a metric space, partitioned into groups, $X_1,\dots,X_m$, and integer quotas, $k_1,\dots,k_m$, summing to $k$, the Fair Max-Min Diversification problem asks for a set of $k$…The directed temporal exploration problem
We study the temporal exploration problem on temporal digraphs.Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory.A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP
Karlin, Klein, and Oveis Gharan introduced a randomized better-than-$3/2$ approximation algorithm for metric TSP [KKO21] and subsequently established the corresponding improvement in the integrality…Distributed Lower Bounds via Automatic Self-Reduction
The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distributed setting and…Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm
Given an undirected weighted graph $G$, a $γ$-approximate low-stretch spanning tree (LSST) $T \subseteq G$ is a tree that approximates the distance metric of $G$ up to a $γ$-factor in expectation.A $5/2$-Approximation for Weighted Ultrametric Embedding with Outliers
Weighted ultrametric embedding with outliers asks for a minimum weight set of points whose deletion makes the remaining metric an ultrametric, equivalently, leaves no triple with a unique largest…Truthful-in-Expectation MMS Allocations for Chores
We study truthful-in-expectation (TIE) mechanisms for allocating indivisible chores alongside ex-post maximin share (MMS) guarantees.Pure Tail Constraints for Online Problems
Controlling tail risk is an important objective in online optimization, and recently it has been studied in the context of competitive analysis.A polylogarithmic higher-order Cheeger inequality
Let $λ_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph, and let $ρ_G(k)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex…