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 4
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp…Efficient Scalable Oversight via Rewinding
Scalable oversight asks how a weak verifier can check the outputs of computations performed by more powerful AI systems.On the Quantum Chromatic Gap II
We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's $d$-to-$1$ games: for every $d\geq 4$, every $ε>0$, and every $k\in\mathbb N$, there is a…What Can Be Computed with Indefinite Causal Structure?
Can quantum computation become more powerful when operations do not need to follow a definite causal order?Clifford synthesis is NP-complete
We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest.Faster #PPM from faster #3SAT
The counting variant (#PPM) of the permutation pattern matching (PPM) problem asks for the number of occurrences of a permutation pattern in a host permutation of length $n$.Stochastic and Noisy Oracles in Smooth Continuous Optimization
We review models of inexact computational oracles in smooth continuous optimization and their implications for the convergence, computational complexity, and attainable accuracy of optimization…Separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$
We give complexity-theoretic separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$.Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles
In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit.A Witnessing Duality for ReLU Network Depth
A depth lower bound for ReLU networks asserts that every sufficiently shallow network fails on some input.Local Quantum Fault Tolerance Without Expansion
We study fault-tolerant quantum computation using a fixed, local error-correction rule and a geometrically simple code: the cubical $(d,d')$-Toric code with $d',d-d'\geq 2$, including the 4D Toric…Maxwell's equations are universal for sparse linear algebra
Optical and wave-based analog computing has re-emerged as a route to accelerating linear algebra, with metamaterials and photonic circuits shown to invert matrices and solve integral equations.A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs
The Murty-Simon conjecture states that every $n$-vertex diameter-$2$-critical graph has at most $\lfloor n^2/4 \rfloor$ edges, with equality only for the balanced complete bipartite graph.Impossibility of No-Regret in Multi-Agent Bidding
We consider $T$ repeated second-price auctions across $n$ pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously…Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
We establish an equivalence between matrix samplers and quantum-proof randomness extractors.Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions.Lower Bound for Region of Non-Distillable Magic States
Magic states are a leading proposal for realizing fault-tolerant and universal quantum computation.The Complexity of Value Optimization in Sporadic Task Systems
Value-based Task Selection (VTS) asks whether a real-time system can select tasks whose total value reaches a required target while preserving every deadline.Linear Hashing Is Poissonesque
The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent…Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set
We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem.