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 8
Cardinalities of Kiselman monoids and their parity asymptotics
The cardinalities of Kiselman's semigroups $K_n$ are known to grow double exponentially in $n$: the sequence $2^{-n/2}\log_2|K_n|$ converges along the even and odd $n$ subsequences to positive…Restricting Odd Antiholes in Critical Graphs via List Coloring
By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole.A QPTAS for Stochastic Scheduling of Bernoulli Jobs
We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time…A Catalytic Algorithm for Transposing Unknown Qutrit Unitaries with Tight Query Bounds
We construct exact deterministic circuits for transposing and inverting an unknown qutrit unitary $U\in\mathrm{SU}(3)$ using only forward queries.Uniqueness for tv-regularized inverse problems with source in divergence form
Inverse source problems in divergence form consist in finding a vector field with prescribed support S, whose divergence is the Laplacian of some observed potential.Predictable Accuracy of Martini 3 Absolute Protein-Ligand Binding Free Energies across 15 Targets
Alchemical free-energy calculations predict protein-ligand binding affinities with close-to-experimental accuracy, but their cost restricts them to small sets of ligands.Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration
The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation.The rank of 3x3 matrix multiplication over F2 is 23
The rank of the tensor of 3×3 matrix multiplication over the field with two elements is at most 23 by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least 22.Quantum Approximation Complexity of Classical Optimization Problems
Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation.A deterministic algorithm for signing bipartite graphs at the Ramanujan bound
We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs.The Multiple Unicast Conjecture is False
The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow.Polynomial Kernels for Interval Completion
An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval graph by adding at…Subset Sum via Partial Match
We show that the subset sum problem can be solved in time $O(2^{0.499999n})$, breaking the $2^{n/2}$ meet-in-the-middle barrier.Verification and Self-Improvement in Agentic AI: Foundations and Limits
Agentic AI systems can improve by searching longer, receiving additional support, or modifying how they propose and verify outputs.$Ω((\log n/\log\log n)^2)$ Lower Bounds for Dynamic Graph Problems
We prove an $Ω((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed…Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
Network coding lets the nodes of a network combine messages rather than merely forward them.A Fast Algorithm for Maltsev Constraints
The constraint satisfaction problem over a set of relations $Γ$ (CSP($Γ$)) is the computational problem of deciding if a set of constraints admits at least one solution.On the complexity of the single-move labeled token routing problem
In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom.On the Computational Complexity of Hidden Markov Model Identification
Identification is the task of recovering the parameters of an unknown ground-truth model from sampled data.Breaking the Space Barrier and its Application to Language Model Inference
Language models are more and more often asked for structured output: JSON that follows a schema, or a tool call with typed arguments.