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-51 Capacity of the Binary Deletion Channel
- CS-52 Perfect-Matching Search in Deterministic NC (General Graphs)
- CS-53 All-Pairs Shortest Paths in Truly Subcubic Time
- CS-54 Exact satisfiability threshold for random k-SAT for small k (k = 3)
- CS-55 Quantum versus Classical Communication Complexity of Total Functions
- CS-56 Reliability Function of the Binary Symmetric Channel Below the Critical Rate
- CS-57 RL versus L
- CS-58 Constant-Query Locally Decodable Codes with Polynomial Blocklength
- CS-59 The k-Server Conjecture for General Metric Spaces
- CS-60 Classical Worst-Case Hardness Reduction for LWE
- CS-61 MAJORITY is not in ACC0
- CS-62 Polynomial-Time Decidability of Semidefinite Programming Feasibility
- CS-63 Polynomial-time explicit logarithmic Ramsey graphs
- CS-64 Deterministic polynomial-time exact bipartite matching
- CS-65 Bodirsky-Pinsker Tractability Conjecture for Infinite-Domain Constraint Satisfaction
- CS-66 Sample Compression Conjecture (Linear Size in VC Dimension)
- CS-67 The Dynamic Optimality Conjecture for Splay Trees
- CS-68 Unrestricted Linear-Circuit Lower Bound for the Discrete Fourier Transform
- CS-69 10 Lectures and 42 Open Problems — The Grothendieck Constant
- CS-70 The Online Boolean Matrix-Vector Multiplication Conjecture
- CS-71 Worst-case to average-case hardness reduction for the Learning Parity with Noise problem
- CS-72 Real $\tau$-Conjecture for Sparse Polynomial Sums and Products
- CS-73 Existence of a p-Optimal Propositional Proof System
- CS-74 NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph
- CS-75 Černý Conjecture on Shortest Reset Words of Synchronizing Automata
- CS-76 Computability of the Shannon Capacity of Finite Graphs
- CS-77 Fourier Entropy-Influence Conjecture
- CS-78 Polynomial-Time P-Matrix Linear Complementarity Problem
- CS-79 Matroid Secretary Conjecture
- CS-80 Deterministic Linear-Time Minimum Spanning Tree Problem
- CS-81 Li-Li Undirected Multiple-Unicast Network Coding Conjecture
- CS-82 Capacity Region of General 3-Receiver Discrete Memoryless Broadcast Channels
- CS-83 Polynomial-Time Solvability of Condon's Simple Stochastic Games
- CS-84 Combinatorial Boolean Matrix Multiplication in Near-Linear Time
- CS-85 Smale's 9th Problem: Linear Programming in Polynomial Time
- CS-86 Sums of independent random variables with unbounded variance
- CS-87 Exponential Algorithms for Knapsack
- CS-88 The robustness of the tensor product
- CS-89 Subset-sums equality (pigeonhole version)
- CS-90 Complexity of square-root sum
- CS-91 Linear-size circuits for stable $0,1 < 2$ sorting?
- CS-92 Discrete Logarithm Problem
- CS-93 Unconditional derandomization of Arthur-Merlin games
- CS-94 Point Location in 3D Subdivision
- CS-95 Flip Graph Connectivity in 3D
- CS-96 Hamiltonian Tetrahedralizations
- CS-97 The Number of Pointed Pseudotriangulations
- CS-98 Sorting $X+Y$ (Pairwise Sums)
- CS-99 10 Lectures and 42 Open Problems — Hardness at the Cheeger square-root gap
- CS-100 10 Lectures and 42 Open Problems — Deterministic Restricted Isometry Property matrices