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 7
Query Complexity of Densest Sub(hyper)graph Problems
Rubinstein et al. introduce the study of connectivity and minimum cut problems in the cut query model, where an algorithm can only access the edges of a graph through CUT queries.Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients.Hitting Minors: Stronger Lower Bounds
For a fixed finite collection of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$, whether there is a set $S\subseteq V(G)$ with…Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity
The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide range of search…$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation
We construct Clifford+$T$ circuits implementing arbitrary $n$-qubit unitaries with worst-case $T$-count $\widetilde{O}(N^{8/7})$ at constant operator-norm error, where $N=2^n$, improving the…On Collusion-Free Teaching in Planar Graphs
Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion.Exploring Minimal Blocking Sets for Kernelization Lower Bounds for $\mathcal{F}$-Minor Deletion
For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$.Bipartite Matching with Few Rounds of Demand Queries
We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds.Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
The Tarski fixed-point problem asks for a fixed point of a monotone map on a $k$-dimensional grid lattice of width $n$ and has applications in game theory, economics, and verification.Graph determination problem from knowledge of its subgraphs
In the context of graph reconstruction studies, this paper addresses the problem defined as follows: given a sample of vertex-coloured graphs, each associated with a number, does there exist a…Learning, Compression, and Meta-Complexity
The idea that learning is closely tied to compression has long served as both a powerful principle and, at times, an informal analogy across machine learning and learning theory.Two Linear Programs are Better than One
The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it.Ordinary and measurable colorings of Euclidean three-space
A proper coloring of Euclidean space is a coloring that assigns different colors to points at distance one.Coarse-Graining Recursive Expert Computation: Continuation-Relative Interfaces and Failure Modes
Computational coarse-graining aims to replace a sequence of updates with a cheaper module while preserving task performance.A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering
Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother…Adjoint Transfer and Order-Lifting Dichotomies for 2 x 2 Matrices over Prime-Power Rings
For an odd prime p, we study the change in matrix order under lifting from Z/p^k Z to Z/p^(k+1) Z. The first variation of the order defect is an affine translate of a cyclic adjoint transfer on…Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for…Quantum Query Complexity of Maximum Degree and its Generalizations
We study the quantum query complexity of several basic graph problems.Bipartite Carrier Compression and Machine-Certified Bounds in Schönhage Trilinear Multiplication Tensors
Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log…A splitting proximal method in portfolio optimization with entropic value-at-risk
Motivated by a recent paper where a convex portfolio optimization problem formulated by means of the entropic value-at-risk is solved via a primal-dual interior-point method, we propose an…