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 2
A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs
A \emph{rainbow cycle} in a list-edge-colored graph is a cycle where no color appears more than once.Finding Hypercliques Faster Than Brute Force
We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in…Universal Hardness From Masking Channels
We prove a broad learning-theoretic generalization of the celebrated hardcore lemma concerning the average-case complexity of computing a Boolean function (Impagliazzo, 1995).Quantum Advantage has Few Complexity Implications
We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation.Agnostic Learning by Imitating
Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive…Breaking the quantum barriers for Graph Collision
In the graph collision problem, the task is to decide whether a known graph on $n$ vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked…Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations
The Multiway Cut problem is among the most well-studied problems in the area of combinatorial approximation algorithms.Efficient Proper Agnostic Learning of Halfspaces
We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on $\{\pm1\}^n$.State Synthesis with an NP oracle
In this note, I describe a quantum algorithm that prepares an arbitrary state $|ψ\rangle$ to inverse exponential precision in polynomial time by making queries to an $\mathsf{NP}$ oracle, assuming…Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting
We study circuit lower bounds for extended gate bases using exact CNF counting and an extension-ring form of the contraction theorem of OpenAI.Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion
We determine the information complexity of matrix multiplication over finite fields under independent uniform inputs, up to a universal additive constant.Fine-Grained Complexity Across the Computational Phase Transition
How does a computational problem transition from easy to hard?Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification
We study the iterates of a fixed ReLU network $N$ of width 4, that is, the discrete-time system $x_{k+1} = N(x_k)$ on $[0,1]^4$.Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs
We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and…Worst-Case to Average-Case Reductions for Basic Linear Algebra
We study worst-case to average-case reductions for basic linear-algebraic problems over finite fields.Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs
We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{Ω(\sqrt{k})}$.Dissecting Geometric Constraints in Grokking: Interaction-Dependent Acceleration in Modular Arithmetic
Spherical transformer configurations can accelerate grokking through simultaneous modifications of several model properties.Online Algorithms Cannot Find Isolated Perceptron Solutions
The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\lfloor αn\rfloor$-many independent random Gaussian half-spaces.Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex.Tilted Convexity and an Exact Offline-Online Separation
Convexity has three equivalent descriptions: support by affine functions, monotonicity of the subdifferential, and increasing secant slopes.