计算复杂性：2025–2026 年度综述

An annual survey of the cs.CC arXiv category, covering research published from September 2025 – August 2026. Built on a close-reading set of 120 papers and organised into 44 chapters, it maps the year by the field's research sub-directions.

Book framework (share of the year's output):

• Classical NP-Hardness and Polynomial-Time Complexity (19.0%) — Investigates the boundaries of polynomial-time solvability and NP-hardness for combinatorial and algebraic problems, often with tight ETH-based lower bounds.
• Parameterized Graph Algorithms and Structural Complexity (14.9%) — Studies parameterized algorithms and hardness results for graph problems, focusing on structural parameters like treewidth, twin-width, and pathwidth.
• Computational Learning Theory and Neural Network Verification (13.5%) — Explores the computational complexity of learning models, neural network verification, and reasoning under probabilistic and adversarial settings.
• Approximation Algorithms and Streaming Complexity (12.5%) — Develops approximation algorithms and space-efficient streaming methods for optimization and counting problems, often with submodular or constraint-satisfaction structures.
• Quantum Algorithms and Quantum Advantage (11.0%) — Analyzes quantum computational advantages and limitations, designing quantum algorithms for problems ranging from spin systems to game equilibria.
• Circuit Lower Bounds and Algebraic Complexity (8.2%) — Proves lower bounds on circuit size, depth, and algebraic complexity measures, including connections to proof complexity and arithmetic circuits.
• Query and Communication Complexity of Boolean Functions (6.7%) — Studies query and communication complexity bounds for testing properties of Boolean functions, including monotonicity, unateness, and linearity.
• Matrix and Tensor Rank Complexity (5.4%) — Investigates computational problems related to matrix and tensor rank, including decomposition, isomorphism, and their implications for algebraic complexity.
• Low-Degree Polynomial Testing and Average-Case Hardness (4.8%) — Examines testing and recovery of low-degree polynomials, with connections to average-case hardness and planted problems in high dimensions.
• Interactive Proofs and Complexity Class Separations (3.9%) — Studies interactive proof systems, oracle separations, and structural properties of complexity classes such as QIP, BQP, and related hierarchies.

Each sub-direction is covered across three chapters — how it framed its questions, the strength of its key findings, and its open debates and frontiers — so the reader gets a traceable picture of what this part of the field actually produced over the year.