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-91 Linear-size circuits for stable $0,1 < 2$ sorting?
- CS-93 Unconditional derandomization of Arthur-Merlin games
- CS-99 10 Lectures and 42 Open Problems — Hardness at the Cheeger square-root gap
- CS-111 Arithmetic-Formula Lower Bounds for Permanent and Determinant
- CS-113 Unique Games Approximation-Threshold Conjecture
- CS-115 $d$-to-$1$ Games Conjecture
- CS-129 Constant-factor hardness of directed feedback vertex set
- CS-131 Counting-hierarchy upper bound for existential-universal real sentences
- CS-132 Explicit super-square-root-exponential depth-three circuits
- CS-134 Unconditional time lower bounds for fixed-dimensional WL
- CS-137 Depth-five homogeneous lower bounds for iterated matrix multiplication
- CS-139 Exponential semidefinite complexity for perfect matching
- CS-140 Optimal Max-Cut approximation hardness
- CS-144 Constant-factor hardness of Min-UnCut
- CS-150 Perfect-completeness two-to-one hardness
- CS-152 Cubic border-determinantal lower bound for the permanent
- CS-154 Average sensitivity of polynomial threshold functions
- CS-156 Quasilinear robust PCP for PPAD
- CS-160 Quadratic sensitivity versus block sensitivity
- CS-164 Independent-set hardness with a three-colorability promise
- CS-169 Constant-factor hardness of uniform sparsest cut
- CS-171 EXPTIME-completeness of variable-dimensional WL
- CS-172 Factor-two hardness of Vertex Cover
- CS-174 Complexity of Weisfeiler–Leman graph identification
- CS-183 Hartmanis–Stearns conjecture
- CS-189 10 Lectures and 42 Open Problems — Consistency and sample complexity of Multireference Alignment
- CS-215 Markov-basis complexity depends on representation
- CS-267 Approximability and Parameterized Complexity of Steiner Forest
- CS-268 Hardness of the $\varepsilon-Dense$ Steiner Tree Problem
- CS-269 Complexity and Approximation of Planar Min-Bisection
- CS-275 Polynomial Complexity of Greedy Lattice Reduction
- CS-279 Computational Hardness of Learning Parity with Noise
- CS-280 Quantum Hardness of Approximate Lattice Problems
- CS-281 Three-Terminal Distance-Interdiction Complexity
- CS-287 Complexity of Dense Perfect Hypergraph Matching
- CS-288 Separation of Constant-Free Valiant Classes
- CS-289 Optimal Algebraic Immunity of Boolean Functions
- CS-297 Rotational Matching Complexity for Planar Point Sets
- CS-306 Sensitivity Growth Under Boolean Conjunctions
- CS-307 Orbit-Closure Obstructions for Permanent–Determinant Separation
- CS-316 Worst-Case Inputs for Smoothed Caching Complexity
- CS-323 Complexity of Maximizing Initial Odd Ears
- CS-328 Complexity of Embedding Two-Complexes in Three-Manifolds
- CS-329 Complexity and Rank of Completely Positive Matrices
- CS-334 Randomized Communication Complexity of Distributed Triangle Detection
- CS-335 Overlap Gaps and Algorithmic Hardness of Submatrix Detection
- CS-337 Complexity of Bray’s Involution-Centralizer Algorithm
- CS-342 Round Complexity of Non-Malleable Commitments
- CS-343 Average-Case Hardness of Quasi-Cyclic Code Problems
- CS-344 Sampling Complexity of Hyperbolic-Cross Approximation