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 6
Deterministic Shift Equivalence Testing for Sparse Polynomials
We study the shift equivalence testing problem for high-degree sparse multivariate polynomials.Approximating Independent Sets Using Additive Combinatorics
We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph.Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime
The class $\mathsf{PPP}$ captures fundamental total search problems, for which a solution is guaranteed to exist by the pigeonhole principle and the main challenge is to find it.Formally Verified Autoresearch for Analyzing the Expressivity of Multi-Head Attention
Multi-head attention is a central component of the transformer architecture, yet how its expressivity depends on the number of heads remains poorly understood.Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
We show that adding "catalytic space" (which starts full and must have its original contents restored at the end of computation) provably speeds up time-and-space-bounded computation.Energy-optimal scheduling for clocked reversible computing
Computational dissipation may arise from both information erasure and finite-time operation, although both contributions can in principle be avoided in the absence of space and time constraints.Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$
Let \(f = \text{EXACT}^5_{3,4}\) be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4.Improved Space Bounds for Promise Graph Coloring in Adversarial Streams
We study promise graph coloring in one pass insertion-only adversarial streams.BQP^cc is not contained in MA^cc
We exhibit a bipartite language with a poly-logarithmic quantum communication protocol and polynomial Merlin-Arthur communication complexity.Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly…Unconditional Quantum PAC Learning Advantage in the Large Error Regime
We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime.Electrostatic Limits on Quantum Spatial Search
We prove that a quantum walker cannot search a two-dimensional lattice in Grover's $O(\sqrt N)$ time, resolving the long-standing open question posed by Aaronson and Ambainis in 2003.The maximum number of Hamiltonian cycles in tournaments
Let $C(n)$ denote the maximum number of directed Hamiltonian cycles in a tournament on $n$ vertices.Strong $\mathfrak{sl}_2$ Actions and Symmetric Chain Decompositions
We introduce a notion of a strong $\mathfrak{sl}_2$-action on a poset, and conjecture the existence of such an action is equivalent to the existence of a symmetric chain decomposition of that poset.Parallel Repetition for Entangled Games via Conditional Relative Entropy
We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy.Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter
We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer $k$ and a simple, undirected, and unweighted graph $G$, the objective is to decide…Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space
Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics.Undirected Network Coding and Faster External-Memory Integer Sorting
Network coding allows intermediate nodes to combine messages.On the Complexity of Linear Programs with Parametric Constraint Matrices
While sensitivity analysis for linear programs with parametric right- hand side vectors is well established, cases involving parametric constraint matrices remain less explored.Connectivity keeping pendant extensions of paths in $k$-connected triangle-free graphs
Motivated by Mader's conjecture on connectivity keeping trees, we study the corresponding problem in triangle-free graphs.