Mathematics Problem Archive

Does $P = NP$? More formally: if the solution to a problem can be quickly verified (in polynomial time), can the solution also be quickly found (in po...

For certain constraint satisfaction problems (unique games), it is NP-hard to approximate the maximum fraction of satisfiable constraints beyond a cer...

The diameter of the graph of a $d$-dimensional polytope with $n$ facets is bounded by a polynomial in $d$ and $n$....

Find efficient algorithms for deciding whether a polynomial with integer coefficients has an integer root....

Find a strongly polynomial algorithm for linear programming....

Determine whether algebraic geometry can systematically replace linear algebra in optimization....

Develop the mathematics required to control the quantum world for computation....

Create scalable mathematics for differential games, replacing traditional PDE approaches....

Develop asymptotics for systems with massive degrees of freedom....

Use mathematical duality and geometry as foundations for developing novel computational algorithms....

Find lower bounds for sensing complexity as data collection grows, addressing entropy maximization....

Conjecture If $X_1, \dotsc, X_n \geq 0$ are independent random variables with $\mathbb{E}[X_i] \leq \mu$, then $$\mathrm{Pr} \left( \sum X_i - \mathbb...

Problem Is P = NP?...

Conjecture The famous 0-1 Knapsack problem is: Given $a_{1},a_{2},\dots,a_{n}$ and $b$ integers, determine whether or not there are $0-1$ values $x_{...

Problem Given two codes $R,C$, their Tensor Product $R \otimes C$ is the code that consists of the matrices whose rows are codewords of $R$ and whose ...

Problem Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$. It follows from the pigeon-hole principle that there exist dist...

Question What is the complexity of the following problem? Given $a_1,\dots,a_n; k$, determine whether or not $\sum_i \sqrt{a_i} \leq k.$...

Problem Can $O(n)$-size circuits compute the function $f$ on $\{0,1,2\}^*$ defined inductively by $f(\lambda) = \lambda$, $f(0x) = 0f(x)$, $f(1x) = 1f...

If $p$ is prime and $g,h \in {\mathbb Z}_p^*$, we write $\log_g(h) = n$ if $n \in {\mathbb Z}$ satisfies $g^n = h$. The problem of finding such an int...

Problem Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, ...

Conjecture One-way functions exist....

Problem Prove unconditionally that $\mathcal{AM}$ $\subseteq$ $\Sigma_2$....

Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a de...

Conjecture For every rational $\epsilon > 0$ and every rational $\Delta$, there is no polynomial-time algorithm for the following problem. Given is a...

Consider a $A\in\mathbb{C}^{M\times N}$ obtained by sampling random rows of a Discrete Fourier Tranform. How large does $M$ need to be in order for, w...

How many mutually unbiased bases are there in 6 dimensions?...

What is the approximation ratio (or integrality gap) for the Sum-of-Squares (SOS) relaxation of degree 4 for the Max-Cut problem? What about other con...

What is the value of the (real) Grothendieck constant?...

What is the clique number of the Paley graph? Can the the SOS degree 4 analogue of the theta number help upper bound it?...

Is there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle?...

Is there an $O(n)$-space data structure that supports $O(\log n)$-time point-location queries in a three-dimensional subdivision of $n$ faces?...

Is the flip graph connected for general-position points in $\mathbb{R}^3$? Given a set of $n$ points in $\mathbb{R}^3$, the flip graph has a node for ...

Can every convex polytope in $\mathbb{R}^3$ be partitioned into tetrahedra such that the dual graph has a Hamiltonian path?...

Is it true that every two sets of $n$ planar points in general position with the same number points on their convex hulls have compatible triangulatio...

For a planar point set $S$, is the number of pointed pseudotriangulations always at least the number of triangulations? A pseudotriangle is a planar p...

Given 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 ...

Given a prime modulus $p$, a group generator $g$, and the public values $g^a$ and $g^b$ modulo $p$, can the shared value $g^{ab}\bmod p$ be computed e...

If the base-$b$ expansion of a real number can be emitted in real time by a multitape Turing machine (bounded time between successive digits), must th...

Give a rigorous explanation for why SnapPy works so well in practice....