Algorithms and data structures
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.
91 records · Search and filter
- CS-32 Graph Isomorphism in Polynomial Time
- CS-41 Randomized Integer Word-RAM 3SUM Conjecture
- CS-45 Polynomial-Time Quantum Algorithm for Symmetric-Group Hidden Subgroups
- CS-46 Omega(n log n) Boolean Circuit Lower Bound for Integer Multiplication
- CS-47 Metric TSP Subtour LP Integrality Gap Conjecture
- CS-49 Polynomial-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- CS-52 Perfect-Matching Search in Deterministic NC (General Graphs)
- CS-53 All-Pairs Shortest Paths in Truly Subcubic Time
- CS-59 The k-Server Conjecture for General Metric Spaces
- CS-64 Deterministic polynomial-time exact bipartite matching
- CS-67 The Dynamic Optimality Conjecture for Splay Trees
- CS-70 The Online Boolean Matrix-Vector Multiplication Conjecture
- CS-80 Deterministic Linear-Time Minimum Spanning Tree Problem
- CS-84 Combinatorial Boolean Matrix Multiplication in Near-Linear Time
- CS-85 Smale's 9th Problem: Linear Programming in Polynomial Time
- CS-87 Exponential Algorithms for Knapsack
- CS-89 Subset-sums equality (pigeonhole version)
- CS-91 Linear-size circuits for stable $0,1 < 2$ sorting?
- CS-98 Sorting $X+Y$ (Pairwise Sums)
- CS-105 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
- CS-106 Dynamic Planar Nearest Neighbors
- CS-114 Polynomial Algorithms for Mean-Payoff Games and Linear Programming
- CS-117 Finite-field polynomial multiplication and integer-multiplication lower bounds
- CS-118 Polynomial switch-chain mixing for all degree sequences
- CS-119 Matrix-multiplication improvement over every field
- CS-122 FPRAS for cell-bounded contingency tables
- CS-123 FPRAS for common integer polymatroid bases
- CS-124 FPRAS for common matroid bases
- CS-125 Complex square and rectangular multiplication bounds
- CS-126 Complex matrix multiplication at exponent nine-fourths
- CS-130 Almost-linear edit-distance approximation scheme
- CS-135 FPRAS for perfect matchings in general graphs
- CS-137 Depth-five homogeneous lower bounds for iterated matrix multiplication
- CS-138 Integer multiplication below n log n
- CS-139 Exponential semidefinite complexity for perfect matching
- CS-140 Optimal Max-Cut approximation hardness
- CS-151 Entropy bounds at perfect-matching marginals
- CS-153 Worst-case Subset Sum below the half exponent
- CS-157 Almost-linear maximum-cardinality matching
- CS-158 Randomized k-server with squared-logarithmic ratio
- CS-161 Factor-two shortest common superstring
- CS-163 Low-space worst-case Subset Sum at half-exponential time
- CS-167 Uniform finite-metric randomized k-server implementation
- CS-270 An FPAS for Constrained Bicriteria Spanning Trees
- CS-271 Output-Polynomial Enumeration of Bicriteria Spanning Trees
- CS-283 Integral Primal Certificates for Submodular Minimization
- CS-284 Recognition and Characterization of Leaf Powers
- CS-285 Sampling Algorithms for Maximum-Cut Density
- CS-286 Codegree Thresholds for Hypergraph Matchings
- CS-287 Complexity of Dense Perfect Hypergraph Matching