Mathematics Problem Archive

Does there exist $c>0$ such that it is NP-hard, given a graph $G$ and $\phi>0$, to distinguish $h_G\le\phi$ from $h_G\ge c\sqrt{\phi}$?...

Given a symmetric matrix ${M}$ with small condition number, is there a quasi-linear time (on ${n}$ and the number of non-zero entries of ${M}$ ) proce...

Let ${G=(V,E,W)}$ be a graph and ${k}$ a positive integer, is the following true? $\rho_G(k) \leq \mathrm{polylog}(k) \sqrt{\lambda_k}. \ \ \ \ \ (2)$...

Construct deterministic matrices $A\in\mathbb{C}^{M\times N}$ (or $A\in\mathbb{R}^{M\times N}$ ) satisfying the $(s,\frac13)$ -RIP for $s\approx\frac{...

Let $N = 2M$ . For which $s$ is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix $A$ is ...

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

Does the Paley Equiangular tight frame satisfy the Restricted Isometry Property pass the square root bottleneck? (even by logarithmic factors?)....

Give a (polynomial time) construction of the tight frame partition satisfying the properties required in the Kadison-Singer problem (or the related We...

Explicit deterministic constructions of codes achieving the GV bound Is the GV bound tight?...

Prove or disprove: $R_A(\alpha n,\beta n,n)=\alpha+(1-\alpha)R_A(1,\beta n,(1-\alpha)n)+o(1)$....

What are the asymptotics of $\mathcal{D}\left(n;\frac12\right)$ ? \item An interesting aspect of the Deletion Channel is that different messages may h...

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

Given a $d$ -regular graph on $n$ nodes $G$ . Let $MaxBis(G)$ and $MinBis(G)$ denote, respectively, the size of its largest and smallest bisection. Is...

Does the projected power method converge (with high probability) to the optimal solution of the angular synchronization problem with (small enough) ga...

Is the SDP for angular synchronization tight (with high probability) for noise levels $\sigma$ essentially until the solution of angular synchronizati...

For which levels of noise is the SDP for Multireference Alignment tight?...

Is the Maximum likelihood for Multireference Alignment consistent? (after fixing the power spectrum) What is the sample complexity of the Multireferen...

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

Is there a data structure maintaining a set of $n$ points in the plane subject to insertions, deletions, and nearest-neighbor queries in $O(\log n)$ t...

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

Is there a practical algorithm to test whether a pair of $3$-manifolds are homeomorphic?...

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

Is there an algorithm to detect whether a Heegaard splitting is reducible and, if so, find a reducing curve?...