Mathematics Problem Archive

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