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 3
Get Permanent Results Faster by Counting Stars
We show that $n \times n$ permanents can be computed with $O^*{(2-\varepsilon)^n}$ arithmetic operations over every commutative ring, for $\varepsilon = 10^{-40}$.A King for Almost Everyone
A tournament is an orientation of a complete graph.On the optimality of truncation among binary linear sketches
We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity measurements.The Complexity of ReLU Network Synthesis from a Parameter Multiset
We ask how hard it is to build a ReLU network when its parameter values are given in advance.An $\mathsf{FPRAS}$ for Mixed Volumes
We design the first fully polynomial-time randomized approximation scheme ($\mathsf{FPRAS}$) to estimate the mixed volume of $n$ arbitrary compact convex sets in $\mathbb{R}^{n}$ specified by weak…Quantum Lower Bounds for Collision Problems
We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\in\mathbb Z_q^n$, for every fixed…Limits and Constants of OpenAI's Claimed ETH Refutation
A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a $k$-CNF formula in time $2^{O_k(n\log\log n/\sqrt{\log n})}$, and $2^{O(n/\sqrt{\log n})}$ at…Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
Given a quantum adversary that queries a random oracle, how do we characterize the information that they "know"?Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization
Constrained quantum samplers often produce infeasible outputs that retain information about good feasible solutions.Approximate clearing in financial networks with credit default swaps: hardness thresholds, a box algorithm, barriers, and exact solvency at bounded degree
We study approximate clearing in financial networks with credit default swaps.The Value of Steiner Hubs in Two-Hop Distance Labeling
Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying…The Movement Complexity of Sorting
The complexity of sorting is usually measured by the number of comparisons.A Numerical Refinement of an Exact Discrete Fourier Transform Bound
We refine the numerical bounds in Kartal's instantiation of Sussman's exact discrete Fourier transform construction.A Decomposition Theorem and a Simple Algorithm for Contraction Fixed Points
We prove a decomposition theorem for the problem of computing an approximate fixed point of a contraction map $f\colon [0,1]^k \to [0,1]^k$ under the $\ell_{\infty}$-norm.Quantum query complexity of Hurwitz stability testing
Determining whether every trajectory of the linear system $\dot{x}=Ax$ converges to zero (or, equivalently, whether $A$ is Hurwitz stable) is a fundamental problem in control theory.Lowered crossover points of Anthropic's subexponential 3-SAT algorithm
The October 2026 refutations of the Exponential Time Hypothesis count satisfying assignments in time $2^{o(n)}$, but an asymptotic bound does not say from which input size, the crossover point, they…Exponential quantum-classical query separations for cyclic Forrelation
We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of $k$-Forrelation [AA15, STOC'15; BS21, STOC'21].Catalytic space-efficient algorithms for Distance and Determinant
Catalytic computation reuses potentially large but in-use space (or catalytic space) which must be restored to its initial contents while the clean space is small.Quantum Query Complexity of Tournament Solutions
A tournament solution records a set of winners from a tournament, that is, from the outcomes of all pairwise comparisons among $N$ alternatives.Retrieval Sequencing in a Compact Storage System with Side Access
In a compact storage system with side access, bins are arranged in adjacent vertical stacks.