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
Asymptotic advantage of quantum one-way and SMP communication for total functions
We exhibit a total Boolean function on n input bits whose bounded-error quantum simultaneous-message (and hence one-way) communication complexity is in O(\sqrt n), whereas its randomised one-way…Structured Quantum Hardness from Unstructured Assumptions
Whether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography.Combinatorial limitations of list-decoding Reed-Solomon codes
For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just…A Universal Threshold Theory for Local Properties of Random Linear Codes
Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes.Randomized Parallel Complexity of Weakly Convex Optimization
We study the minimum number of query rounds needed to find approximate stationary points of nonsmooth weakly convex functions, measured by the gradient of the Moreau envelope.Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum…Polynomial-time classical simulation of boson and fermion sampling under thermal loss
Sampling experiments are a leading approach to demonstrating quantum computational advantage, yet their robustness to experimental noise is not completely understood.Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
We study the query complexity of sampling from smooth distributions on $\mathbb R^d$ using first-order oracles.Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds
Attention is central to modern AI models for language, vision, and scientific modeling.An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine
The halting problem asks whether a program eventually halts, with unrestricted resources.Improved Exact and Approximate Quantum Fourier Transforms from Multiplication
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase…Semidirect sums of tensors and the matrix multiplication exponent
This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent.State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities.Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints
We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of $v$-vertex simple graphs with failure probability at most $δ$.On the Hardness of Approximate Quantum Circuit Membership and Optimization
Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific…Binary Huffman Coding with Unequal Letter Costs Is NP-Complete
Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost.Entropy-Weighted Soundness for Multi-Answer Birthday Graphs
The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables.Abelian embeddings make useful promises: approximation of detrivialised equations
We study the following family of search problems: given a system of equations $x+y+z\equiv 0\pmod p$ promised to admit a solution that is nonconstant on every equation, find a $c$-colouring of the…Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator
We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with…Differentially Oblivious Priority Queues with Sublogarithmic Cost
In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model.