Computational complexity
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
153 records · Search and filter
- Math-4534 Resolution Lower Bounds for Clique Certification
- Math-4545 Hardness of Root-Dependent Spanning-Tree Optimization
- Math-4546 Hardness of Path-Cost Arborescence Optimization
- Math-4549 Real Tau Conjecture for Depth-Four Circuits
- Math-4550 Karchmer–Raz–Wigderson Composition Conjecture
- Math-4553 Sharp Smoothed Complexity of Simplex Pivot Rules
- Math-4557 Sample Complexity of Vertex-Distribution-Free Graph Testing
- Math-4558 Complexity of Approximate Counting in Spin Systems
- Math-4565 Complexity of Submodular $k$-Partition
- Math-4567 Extension Complexity of Inscribed Fixed-Dimensional Polytopes
- Math-4580 Good Locally Testable Quantum Codes and Linear-Rate PCPs
- Math-4584 LOCAL Coloring Complexity and Constant-Round Decidability on Trees
- Math-4585 Algebraic Complexity of Borel Constraint Problems
- Math-4606 Superpolynomial Lower Bounds for Dag-Like Resolution over Parities
- Math-4607 Fractional Coefficient Savings in Algebraic Proof Systems
- Math-4608 Circuit-Size Hierarchy in Bounded Arithmetic
- Math-4614 Unconditionally Ruling Out Heuristica
- Math-4626 Degree Automatability of Sum-of-Squares Proofs
- Math-4627 Complexity-Bounded Computation of Maximum Destabilizing Subgroups
- Math-4637 Hidden-Layer Depth Complexity of Piecewise-Linear Functions
- Math-5167 Sharper Complexity Bounds for Full-Newton Interior-Point Methods
- Math-5174 Hardness of Decoding Random Linear Codes
- Math-5185 Computational Complexity of Bruhat-Interval Invariants
- Math-5186 Semialgebraic Homeomorphism Types at Fixed Complexity
- Math-5187 Boolean Evaluation and Arithmetic-Circuit Complexity
- Math-5198 Polymorphism Characterization of Constraint Approximation Thresholds
- Math-5200 Sample Complexity of Active Coordinate Identification
- Math-5206 Predicting SAT-Solver Hardness from Formula Structure
- Math-5217 Hardness Amplification by Exponent Noise
- Math-5220 Complexity of Extremality Testing in Infinite Group Problems
- Math-5224 Convexification and Complexity in Mixed-Integer Optimization
- Math-5227 Karchmer–Raz–Wigderson Formula Lower-Bound Conjecture
- Math-5229 Refutation Lower Bounds for Random k-SAT Instances
- Math-5230 Depth-Three Lower Bounds for an Explicit Trilinear Function
- Math-5237 Cutting Planes Lower Bounds for Random CNF Formulas
- Math-5239 Random CNF Lower Bounds beyond Cutting Planes
- Math-5245 Provable Advantages of Convolutional Arithmetic Circuits
- Math-5258 Multiplicity Obstructions in Geometric Complexity Theory
- Math-5262 Geometric Analogues of Finite Effective Complexity
- Math-5266 Quantum Complexity of High-Precision Matrix Scaling
- Math-5271 Dimension–Complexity Tradeoffs in Quantum-Function Testing
- Math-5272 Average-Case Metacomplexity Characterizations of One-Way Functions
- Math-5273 Size-Efficient Circuits Resilient to Short-Circuit Errors
- Math-5274 Rank Dependence of Sample Complexity in Matrix Sensing
- Math-5277 Stochasticity and Sample Complexity in Neural Networks
- Math-5278 Open Problems in Local Graph Complexity
- Math-5297 Open Problems in Proof and Computational Complexity
- Math-5298 Coefficient Compression and Structured Proof-System Lower Bounds
- Math-5299 Average-Case Complexity of Clique on Sparse Graphs
- Math-5301 Restriction Condensation of Deterministic Communication Complexity