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 10
W[1]-Hardness of Upper Clique Transversal
A clique transversal of a graph is a set of vertices intersecting every maximal clique.Gap Amplification for Local Hamiltonians with Combinatorial Soundness
The quantum PCP conjecture is one of the major open problems in quantum complexity theory.Training Variational Quantum Algorithms Is NP-Hard, Even Locally
Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits.Optimal and Verifiable Quantum Advantages in Communication Complexity
We establish optimal quantum-classical separations in communication complexity for search problems.Phenomenon-first problem formulation with language models in metal-organic frameworks
Here we introduce a phenomenon-first framework for materials discovery in which an LLM receives separate descriptions of guest physics, host capabilities and operating context and proposes an…A Simple Algorithm Breaking the 1/3 Barrier for Approximate Nash Equilibria in Bimatrix Games
The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for $ε$-approximate Nash equilibria.A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers
Exactly computing the maximum function is a standard test case for studying depth in ReLU networks.Nonuniform QCPH Collapse Implies QCPH Collapse
Despite the importance of the non-uniform Polynomial-Time Hierarchy (PH/poly) in classical complexity understanding the collapse conditions of the Polynomial-Time Hierarchy (PH), a quantum…Quantum Submodular Maximization
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an…Nearly optimal Personalized PageRank computation
We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph $G$.Hamiltonian locality testing and certification do not achieve the Heisenberg limit
We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse.No Size-Preserving Amplification with Quantum Advice
Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005].The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning
We model an academic curriculum as a generator of a language of feasible study plans: prerequisites are monotone Boolean formulas in conjunctive normal form, degree requirements are credit-threshold…Normal-Form Correlation in Markov Games
There has been a surge of recent work on correlated equilibrium concepts in Markov games.Exponential quantum space advantage in random data streams
We show two unconditional quantum space advantages in the random-order streaming model.Unitary complexity in polynomial space
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$.Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
The equalities IP = PSPACE and QIP = PSPACE, the latter achievable with three messages, raise a basic question: how much of an interactive proof's power comes from the underlying physical theory?Exact $T$-counts of CCZ layers from an isotropy bound
The $T$-count is a dominant cost of fault-tolerant Clifford$+T$ computation.Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion
We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $\smash{O(n^{4/23}) = O(n^{0.17391\ldots})}$ colors, improving on the recent bounds…Stable and Online Algorithms for Random Matrix Discrepancy
We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $κ>0$, find signs…