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 13
Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold
Can structural knowledge about a hash function help accelerate the (black box) detection of collisions in it?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.Resonance Breaking in Noisy Shor's Algorithm
We argue that the exponential quantum advantage in Shor's algorithm is broken under one-layer depolarizing noise of arbitrary small error rate, by analyzing a resonance breaking phenomenon in noisy…Optimal Quantum-Classical Separations for Exact Learning
We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{0,1\}^N$, focusing on the relationships among their deterministic, randomized, and quantum query…Ramanujan quantum expanders from the Weil representation
For every odd prime power $q$ and $D=q+1$, we construct an infinite family of Ramanujan quantum expanders of degree $D$.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…There is no $8$-regular $K_3$-irregular graph
A graph is $K_3$-irregular if its vertices belong to pairwise distinct numbers of triangles.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.Depth-Optimal Quantum Compilation
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis.Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied.Distributional Variants of the Aaronson-Ambainis Conjecture
A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms.Sublinear Copies Suffice for Fidelity Estimation with Pauli Measurements
We present a protocol that estimates the quantum fidelity, up to precision $\varepsilon$, between a known target state and unknown lab-prepared state with sublinear, $o(d^{0.9908}/\varepsilon^2)$…Quantum Query Complexity Beyond the Worst Case
Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice.Optimal Query Complexity for Ground-State Preparation
We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known.The lattice of varieties of semigroups with completely regular square. II
We solve (modulo groups) the word problem for free semigroup satisfying $xy = (xy)^n$.An EPTAS for Offline Temporary Tasks Assignment on Few Machines
In offline temporary tasks assignment, each job has a time interval and a positive weight and is assigned to one of $r$ identical machines for its entire interval; the goal is to minimize the peak…The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective
In this paper I revisit my 2006 conjecture on correlated errors in entangled physical qubits, originally proposed as a potential obstruction to quantum fault tolerance.A 51-Addition Alternative-Basis Kernel for Rank-23 $3\times3$ Matrix Multiplication
We give a rank-23 algorithm for $3\times3$ matrix multiplication using 51 additions and subtractions in alternative bases.Parity Tests under Ties: A One-Test Lifting Theorem
In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged.Quantum interaction can superactivate cheating under parallel repetition
We study interactive multiprover games and many-round protocols in which the communication between the verifier and the provers is quantum.