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 16
On testing the incentive compatibility of single-parameter allocation mechanisms
This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive…Structural Parameterizations for Eternal Vertex Cover
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$.Tight Lower Bounds for Algebraic Communication and Applications
Communication complexity studies how much information must be exchanged to solve a problem whose input is split among two or more parties.Products of Boolean Clones up to Minion Homomorphisms
We study the minion homomorphism poset of multisorted Boolean clones.Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
Bilu and Linial conjectured that every finite $d$-regular graph with $d \geq 2$ admits an edge signing $σ$ whose signed adjacency matrix $A_σ$ has spectral radius at most $2\sqrt{d-1}$.Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification
In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-δ$, using as few samples…An endpoint exception to a conjectured equality characterization for Laplacian eigenvalue products
We give eight-vertex counterexamples to the equality characterization in Conjecture 20 of Chen, Guo, Li and Wang, Electron.Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor
We show that there is a fixed planar graph $H$, namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs.Learning Sparse Quantum States
We study the problem of tomography for $k$-sparse quantum states.On the Parameterized Complexity of Coloring Discovery
Coloring Discovery asks whether a possibly improper initial coloring can be made proper within a prescribed number of allowed changes.Subexponential Approximation of the Permanent in Deterministic Polynomial Time
We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor.Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
How much memory is needed to retain the quantum speedup for collision finding?A2ABreak: Systematic Security Analysis of the A2A Protocol
The Agent2Agent (A2A) protocol, now governed by the Linux Foundation, is an open standard that enables autonomous AI agents to discover, authenticate with, and delegate tasks to one another across…Maximum Matching-Match: Hardness and Approximation
In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024).Algorithms for Finite Group Epimorphism Testing
The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$.A construction of F-irregular graphs
For a fixed graph F, the F-degree of a vertex v in a host graph H is the number of subgraphs of H isomorphic to F that contain v, and H is F-irregular if its F-degrees are pairwise distinct.A Near-Linear Element Kernel for \(d\)-Hitting Set
In \(d\)-\textsc{Hitting Set}, the input consists of a finite universe \(U\), a family \(\mathcal S\) of subsets of \(U\) with size at most \(d\), and an integer \(k\).A Lower Bound of 21 for $3\times3$ Matrix Multiplication over $\mathbb{F}_2$
We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$.Improved Multilayered PCPs and Hypergraph Vertex Cover
We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways.Beyond Distance Ordering: Resource Complexity and Universal Optimality of Exact Labeled Directed Shortest Paths
We study exact single-source shortest paths when the output is only the materialized labeled distance vector ($\mathrm{DIST}$), rather than a distance order.