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 15
Good Quantum Locally Testable Codes from Product Expansion
We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes.On the Complexity of Finding Decoherence Free Subspaces
Decoherence free subspaces are a steady-state structure of the open quantum system which preserves quantum coherence between the states lying with in it and thus has found a variety of applications…Quantum Soundness of a Total-Degree Line-versus-Point Test
We prove quantum soundness of the total-degree diagonal line-vs-point test using the individual-degree soundness theorem of Ji, Natarajan, Vidick, Wright, and Yuen.On the Offline Version of the Time-Optimal k-Server Problem
We consider the offline problem of parallel relocation of k identical mobile resources.Near-Optimal Online Metric Matching on $Δ$-ary HST
In the online metric matching problem, we have $n$ servers with known locations in some metric space.A Fixed-Parameter Algorithm for 4-Block Integer Programming
We give a fixed parameter tractable (FPT) algorithm with running time $f(k,Δ)\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$…Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action.Weighted Quantum Signal Processing: Low-Depth Polynomial Approximation with Applications to Kolmogorov-Arnold Networks
Quantum Signal Processing is a powerful quantum framework for generating and approximating univariate polynomials.A lower bound for $\langle 3,2,m \rangle$ matrix multiplication
We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$.Almost Optimal FPT Inapproximability for k-SetCover
We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH.Human Language Shapes the Emerging Physical Reasoning in Large Language Models
Whether large language models (LLMs) acquire adequate representations of physical reality by predicting the next token remains unresolved.Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem.Hidden Circuits and Exact Counting in Ordered Graphs
We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and…Learning Depth-3 Circuits with Polynomial Savings
We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning.Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents
The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns.A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$
We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$.Optimizing Both Checking and Update Costs in Random Walk Search
Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked.CaMeLoT: CaMeL orchestrated with Temporal logic for static verification and liveness
LLM-based agents generate and execute multi-step plans that invoke external tools which can access private data or execute commands.FloatLib: Verified Floating-Point Arithmetic in Lean
We present FloatLib, a verified arbitrary-precision floating-point arithmetic library in Lean 4 that combines broad format coverage, machine-checked correctness, and efficient certified execution.List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$
We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$.