Theory & Algorithms · Computer Science & AI
Computational Complexity
The newest papers in Computational Complexity that ReadSearch has read, newest first. Each links to its own page, with its authors, date, where it was published and the original.
343 papers, from 31 August 2026 to 5 November 2026: 282 arXiv preprints and 61 OpenAlex records.
Get the few papers worth your time in Computational Complexity every morning.
Follow Computational Complexity 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 12
Security Properties of Neural Networks as Decision Problems
Certifying a deployed neural network raises decision problems that the verification literature has not classified: whether the model carries a backdoor planted in its training data, whether a fault…Improved Quantum Random Self-Reduction for Linear Problems
We study quantum random self-reductions for linear problems over finite fields.Verifiable quantum advantage based on polynomials with planted structures
A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just…A mixing time method for estimating the sample complexity of quantum state discrimination
We develop a mixing time method for estimating the sample complexity of quantum state discrimination.A physical and universal model of bosonic computations with Solovay-Kitaev theorem
Bosonic quantum systems are among the leading architectures for quantum information processing, offering continuous-variable degrees of freedom with strong error-correction capabilities.Quantum Algorithms for Minimum Generating Set
In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups.Exponential Quantum Advantage in Numbers-on-Forehead Communication
We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem.Computational Bounds for $f$-Routing
The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited.Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to the SetDisjointness…Planted Cliques and Quantum Symmetry-Adapted Measurements
We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph.Computational Work Extraction: The Complexity of Catalysts
We prove maximal separations: $n$-qubit systems can have $Θ(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms.A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation.Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians.Noisy Quantum Query Complexity via Fractional Block Sensitivity
We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\operatorname{fbs}$).Good Quantum Locally Testable Codes from Lossless Cubical Complexes
Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders.Polynomial-time local-unitary equivalence of graph states
Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits.Sample Complexity of Equivariant Reinforcement Learning
Reinforcement learning (RL) is a powerful framework for robotic control, yet its practical application is often hindered by high sample complexity.Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
The local Hamiltonian problem is the canonical $\mathsf{QMA}$-complete problem, and $O(2^n)$ time classical algorithms and $O(2^{n/2})$ time quantum algorithms are known to solve the problem in the…Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable
We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids $P_k\square P_n$ with at most three colors.Efficiently Approximating Attention Is Hard
Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly.