Mathematics Problem Archive

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

Problem Is P = NP?...

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

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

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 clique number of the Paley graph? Can the the SOS degree 4 analogue of the theta number help upper bound it?...

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