Algorithms and data structures
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. 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
- Math-134 Graph Isomorphism in Polynomial Time
- Math-172 Randomized Integer Word-RAM 3SUM Conjecture
- Math-190 Polynomial-Time Quantum Algorithm for Symmetric-Group Hidden Subgroups
- Math-193 Omega(n log n) Boolean Circuit Lower Bound for Integer Multiplication
- Math-203 Metric TSP Subtour LP Integrality Gap Conjecture
- Math-220 Polynomial-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Math-231 Perfect-Matching Search in Deterministic NC (General Graphs)
- Math-236 All-Pairs Shortest Paths in Truly Subcubic Time
- Math-266 The k-Server Conjecture for General Metric Spaces
- Math-293 Deterministic polynomial-time exact bipartite matching
- Math-310 The Dynamic Optimality Conjecture for Splay Trees
- Math-315 The Online Boolean Matrix-Vector Multiplication Conjecture
- Math-441 Deterministic Linear-Time Minimum Spanning Tree Problem
- Math-484 Combinatorial Boolean Matrix Multiplication in Near-Linear Time
- Math-513 Smale's 9th Problem: Linear Programming in Polynomial Time
- Math-1170 Exponential Algorithms for Knapsack
- Math-1172 Subset-sums equality (pigeonhole version)
- Math-1174 Linear-size circuits for stable $0,1 < 2$ sorting?
- Math-1665 Sorting $X+Y$ (Pairwise Sums)
- Math-2073 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
- Math-2165 Dynamic Planar Nearest Neighbors
- Math-2420 Polynomial Algorithms for Mean-Payoff Games and Linear Programming
- Math-2492 Finite-field polynomial multiplication and integer-multiplication lower bounds
- Math-2960 Polynomial switch-chain mixing for all degree sequences
- Math-2961 Matrix-multiplication improvement over every field
- Math-2964 FPRAS for cell-bounded contingency tables
- Math-2965 FPRAS for common integer polymatroid bases
- Math-2966 FPRAS for common matroid bases
- Math-2967 Complex square and rectangular multiplication bounds
- Math-2968 Complex matrix multiplication at exponent nine-fourths
- Math-2972 Almost-linear edit-distance approximation scheme
- Math-2977 FPRAS for perfect matchings in general graphs
- Math-2979 Depth-five homogeneous lower bounds for iterated matrix multiplication
- Math-2980 Integer multiplication below n log n
- Math-2981 Exponential semidefinite complexity for perfect matching
- Math-2982 Optimal Max-Cut approximation hardness
- Math-2993 Entropy bounds at perfect-matching marginals
- Math-2995 Worst-case Subset Sum below the half exponent
- Math-2999 Almost-linear maximum-cardinality matching
- Math-3000 Randomized k-server with squared-logarithmic ratio
- Math-3003 Factor-two shortest common superstring
- Math-3005 Low-space worst-case Subset Sum at half-exponential time
- Math-3009 Uniform finite-metric randomized k-server implementation
- Math-4459 An FPAS for Constrained Bicriteria Spanning Trees
- Math-4460 Output-Polynomial Enumeration of Bicriteria Spanning Trees
- Math-4472 Integral Primal Certificates for Submodular Minimization
- Math-4473 Recognition and Characterization of Leaf Powers
- Math-4474 Sampling Algorithms for Maximum-Cut Density
- Math-4475 Codegree Thresholds for Hypergraph Matchings
- Math-4476 Complexity of Dense Perfect Hypergraph Matching