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 9
Lower Bounds for Parallel Diffusion Sampling
Standard diffusion samplers generate samples through repeated evaluations of a learned score function.Fine-Grained Hardness of Approximating Dynamic Time Warping
We prove conditional lower bounds for approximating dynamic time warping (DTW) over the uniform metric on three symbols.A faster matrix multiplication algorithm through structured optimization
We present a new asymptotic matrix multiplication construction yielding $ω<2.37115924$, and therefore an algorithm that multiplies two $n\times n$ matrices in $O(n^{2.37115924})$ arithmetic…Inheritance of expansion and oriented Hamilton cycles in robust expanders: a regularity-free proof
Häggkvist and Thomason proved that every $n$-vertex oriented graph with minimum semidegree at least $(\frac{5}{12}+o(1))n$ contains every orientation of a Hamilton cycle.Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
We consider a matching problem in which the cost of each edge is a vector with $k$ components.Unitary RQL Equals RQL
Intermediate measurements let quantum computations discard information and reuse their workspace.Robust subspace designs and the power of a unique small quantum witness
The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13).A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; however, this…Random-Oracle Unitary Synthesis is Impossible
A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in…An FPRAS for Counting Common Bases of Two Matroids
We design the first polynomial-time algorithms for approximately counting and almost uniformly sampling common bases of two matroids given by their independence oracles.Separating ClonableQMA and QCMA Relative to a Classical Oracle
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is…Complexity separations for optimal matchgate-Clifford synthesis
Clifford and matchgate circuits are canonical families of classically simulable quantum circuits.Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial…Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
We study the one-way communication complexity of the $f$-Boolean Hidden Partition problem.Natural proofs for quantum state preparation lower bounds
We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult.Distributional Quantum Query Complexity
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a…Tarski Fixed Points in Quasi-FPT Queries
We study the query complexity of finding a Tarski fixed point over $[n]^k$.Black Hole Radiation Decoding in the Haar Random Oracle Model
We prove optimal query bounds for recovering a single qubit from black-hole radiation in the Haar random oracle model, when the remaining black hole contains at most one sixteenth of the system's…Cores Characterize the One-Pass Streaming Complexity of CSPs
We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied…Non-dyadic Laver algebras
We study finite Laver algebras, the generalizations of Laver tables on sets of cardinality not of the form $2^n$.