Unsolved Problems
Showing 1-8 of 8 problems
Category
Problem Set
Status
The Unique Games Conjecture
For certain constraint satisfaction problems (unique games), it is NP-hard to approximate the maximum fraction of satisfiable constraints beyond a cer...
Smale's 4th Problem: Integer Zeros of Polynomials
Find efficient algorithms for deciding whether a polynomial with integer coefficients has an integer root....
Smale's 9th Problem: Linear Programming in Polynomial Time
Find a strongly polynomial algorithm for linear programming....
Beyond Convex Optimization
Determine whether algebraic geometry can systematically replace linear algebra in optimization....
Game Theory at Scale
Create scalable mathematics for differential games, replacing traditional PDE approaches....
Computation at Scale
Develop asymptotics for systems with massive degrees of freedom....
Computational Duality
Use mathematical duality and geometry as foundations for developing novel computational algorithms....
Occam's Razor in Many Dimensions
Find lower bounds for sensing complexity as data collection grows, addressing entropy maximization....