Computational complexity
The Top Open Problems editorial order restricted to Computer Science, followed by cross-listed economics entries. Existing relative order is retained, with provisional placements for new game-learning questions; most entries have no individual difficulty assessment. 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
- CS-345 Resolution Lower Bounds for Clique Certification
- CS-356 Hardness of Root-Dependent Spanning-Tree Optimization
- CS-357 Hardness of Path-Cost Arborescence Optimization
- CS-360 Real Tau Conjecture for Depth-Four Circuits
- CS-361 Karchmer–Raz–Wigderson Composition Conjecture
- CS-364 Sharp Smoothed Complexity of Simplex Pivot Rules
- CS-368 Sample Complexity of Vertex-Distribution-Free Graph Testing
- CS-369 Complexity of Approximate Counting in Spin Systems
- CS-376 Complexity of Submodular $k$-Partition
- CS-378 Extension Complexity of Inscribed Fixed-Dimensional Polytopes
- CS-391 Good Locally Testable Quantum Codes and Linear-Rate PCPs
- CS-395 LOCAL Coloring Complexity and Constant-Round Decidability on Trees
- CS-396 Algebraic Complexity of Borel Constraint Problems
- CS-417 Superpolynomial Lower Bounds for Dag-Like Resolution over Parities
- CS-418 Fractional Coefficient Savings in Algebraic Proof Systems
- CS-419 Circuit-Size Hierarchy in Bounded Arithmetic
- CS-425 Unconditionally Ruling Out Heuristica
- CS-437 Degree Automatability of Sum-of-Squares Proofs
- CS-438 Complexity-Bounded Computation of Maximum Destabilizing Subgroups
- CS-448 Hidden-Layer Depth Complexity of Piecewise-Linear Functions
- CS-632 Sharper Complexity Bounds for Full-Newton Interior-Point Methods
- CS-639 Hardness of Decoding Random Linear Codes
- CS-650 Computational Complexity of Bruhat-Interval Invariants
- CS-651 Semialgebraic Homeomorphism Types at Fixed Complexity
- CS-652 Boolean Evaluation and Arithmetic-Circuit Complexity
- CS-663 Polymorphism Characterization of Constraint Approximation Thresholds
- CS-665 Sample Complexity of Active Coordinate Identification
- CS-671 Predicting SAT-Solver Hardness from Formula Structure
- CS-682 Hardness Amplification by Exponent Noise
- CS-685 Complexity of Extremality Testing in Infinite Group Problems
- CS-689 Convexification and Complexity in Mixed-Integer Optimization
- CS-692 Karchmer–Raz–Wigderson Formula Lower-Bound Conjecture
- CS-694 Refutation Lower Bounds for Random k-SAT Instances
- CS-695 Depth-Three Lower Bounds for an Explicit Trilinear Function
- CS-702 Cutting Planes Lower Bounds for Random CNF Formulas
- CS-704 Random CNF Lower Bounds beyond Cutting Planes
- CS-710 Provable Advantages of Convolutional Arithmetic Circuits
- CS-723 Multiplicity Obstructions in Geometric Complexity Theory
- CS-727 Geometric Analogues of Finite Effective Complexity
- CS-731 Quantum Complexity of High-Precision Matrix Scaling
- CS-736 Dimension–Complexity Tradeoffs in Quantum-Function Testing
- CS-737 Average-Case Metacomplexity Characterizations of One-Way Functions
- CS-738 Size-Efficient Circuits Resilient to Short-Circuit Errors
- CS-739 Rank Dependence of Sample Complexity in Matrix Sensing
- CS-742 Stochasticity and Sample Complexity in Neural Networks
- CS-743 Open Problems in Local Graph Complexity
- CS-762 Open Problems in Proof and Computational Complexity
- CS-763 Coefficient Compression and Structured Proof-System Lower Bounds
- CS-764 Average-Case Complexity of Clique on Sparse Graphs
- CS-766 Restriction Condensation of Deterministic Communication Complexity