Computer Science catalogue
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.
916 records · Search and filter
- CS-151 Entropy bounds at perfect-matching marginals
- CS-152 Cubic border-determinantal lower bound for the permanent
- CS-153 Worst-case Subset Sum below the half exponent
- CS-154 Average sensitivity of polynomial threshold functions
- CS-155 Matrix hitting points in every positive characteristic
- CS-156 Quasilinear robust PCP for PPAD
- CS-157 Almost-linear maximum-cardinality matching
- CS-158 Randomized k-server with squared-logarithmic ratio
- CS-159 One rational matrix hitting point for noncommutative formulas
- CS-160 Quadratic sensitivity versus block sensitivity
- CS-161 Factor-two shortest common superstring
- CS-162 Quasipolynomial stochastic mean-payoff decision
- CS-163 Low-space worst-case Subset Sum at half-exponential time
- CS-164 Independent-set hardness with a three-colorability promise
- CS-165 Polynomial-time three-machine unit-job scheduling
- CS-166 Polynomial state complementation of two-way NFAs
- CS-167 Uniform finite-metric randomized k-server implementation
- CS-168 Uniform quasipolynomial worst-case trace reconstruction
- CS-169 Constant-factor hardness of uniform sparsest cut
- CS-170 Large Goemans–Linial gaps for uniform sparsest cut
- CS-171 EXPTIME-completeness of variable-dimensional WL
- CS-172 Factor-two hardness of Vertex Cover
- CS-173 Zero dimension exponent for well-conditioned sampling queries
- CS-174 Complexity of Weisfeiler–Leman graph identification
- CS-175 Parity witnesses for Weisfeiler–Leman equivalence
- CS-176 Superpolynomial worst-case trace sample lower bounds
- CS-177 The Polynomial Hirsch Conjecture
- CS-178 10 Lectures and 42 Open Problems — Constructive Kadison-Singer
- CS-179 10 Lectures and 42 Open Problems — Boolean classification and annulus conjecture
- CS-180 10 Lectures and 42 Open Problems — Tightness of the Multireference Alignment SDP
- CS-181 Simple Linear-Time Polygon Triangulation
- CS-182 Compatible Triangulations
- CS-183 Hartmanis–Stearns conjecture
- CS-184 Refuting random 3SAT-instances on $O(n)$ clauses (weak form)
- CS-185 10 Lectures and 42 Open Problems — Certifying that matrices are PSD
- CS-186 10 Lectures and 42 Open Problems — The Paley Clique Problem
- CS-187 10 Lectures and 42 Open Problems — Maximum and minimum bisections on random regular graphs
- CS-188 10 Lectures and 42 Open Problems — Sharp tightness of the Angular Synchronization SDP
- CS-189 10 Lectures and 42 Open Problems — Consistency and sample complexity of Multireference Alignment
- CS-190 Computational Diffie–Hellman problem
- CS-191 8.4 (Schleimer) — Detecting reducible Heegaard splittings
- CS-192 Linear collapse, binomial hypersurfaces, and the image of local-odds fibers
- CS-193 Compatible and complete odds-ratio specifications
- CS-194 Zero patterns, facial sets, and exact support repair in chordal models
- CS-195 Unique minimal Markov bases, bipartite cycles, and padding monotonicity
- CS-196 An algebraic one-mode certificate for MANOVA
- CS-197 Exact slack lifts for Markov bases under rounded summaries
- CS-198 Binary independence and hierarchical models in cumulant coordinates
- CS-199 Holonomic Bayesian normalizers with certified posterior moments
- CS-200 Transcendence-aware algebraic localization of symmetric Gaussian-mixture modes