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 11
Trapdoored Clifford Operators and Applications
Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication.Exponential quantum advantages for decoded quantum interferometry in the streaming setting
Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025).Can AI Oversight Be Zero Knowledge?
AI systems increasingly produce outputs from confidential data, such as a fitness-for-duty assessment from medical records or the predicted properties of a drug candidate from its secret structure.Lower Bounds for Preprocessing Attacks on Quantum Cryptography
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model.Optimal transducers using symmetries
Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an…A provable quantum advantage for approximate optimization via decoded quantum interferometry
Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers.Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth…The Robustness of QAC0
In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set.Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses
We introduce a method for studying state preparation complexity in dense quantum $p$-spin Hamiltonians on $n$ qubits, going beyond bounds based only on circuit lightcones.Polynomial-time classical and quantum simulation of quantum impurity models
Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods.How to Have a Sensitive Debate: An Instance-Optimal Protocol for AI Debate
As powerful AI systems reach and sometimes surpass the abilities of human experts across a range of cognitively demanding tasks, the problem of accurate oversight and supervision of these systems…The complexity of entangled graph colouring via polymorphisms
Constraint satisfaction problems (CSPs) with operator assignments to the variables provide a well-structured setting to study the decision complexity of the entangled value of classes of nonlocal…Approximation and computation of the geodesic Sinkhorn distance
In [H.Towards Strongly Aperiodic Monotiles in Higher Dimensions
The discovery of Chair44 (Tsiokos, 2026) settled the three-dimensional einstein problem with a strongly aperiodic polyhedral monotile in $\mathbb{R}^3$.A Separation Between Types of Quantum Oracle Separations
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks.Experimentally Testable Quantum Advantage in Shallow Circuits
Experimental tests of shallow-circuit quantum advantage require explicit classical bounds at finite circuit sizes.The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute.Information Potential: A Variational Approach to Quantum Information Complexity
Quantum information complexity (QIC), introduced by Touchette [Touchette, STOC 2015], has been shown to be one of the most powerful methods for proving quantum communication complexity and has also…On quantum interactive proofs with a laconic prover
Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting.QMA(2) with Limited Shared Entanglement
A $\mathsf{QMA}(2)$ protocol involves two provers submitting unentangled witnesses to a polynomial-time quantum verifier.