Mathematics Problem Archive
Showing 1-12 of 12 problems
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....
10 Lectures and 42 Open Problems — Mutually Unbiased Bases
v1.3 research notesHow many mutually unbiased bases are there in 6 dimensions?...
10 Lectures and 42 Open Problems — The Grothendieck Constant
v1.3 research notesWhat is the value of the (real) Grothendieck constant?...
Simple Linear-Time Polygon Triangulation
v1.3 research notesIs there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle?...
Sorting $X+Y$ (Pairwise Sums)
v1.3 research notesGiven two sets of numbers, each of size $n$, how quickly can the set of all pairwise sums be sorted? In symbols, given two sets $X$ and $Y$, our goal ...