Mathematics Problem Archive
Showing 1-13 of 13 problems
10 Lectures and 42 Open Problems — Hardness at the Cheeger square-root gap
v1.3 research notesDoes 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}$?...
10 Lectures and 42 Open Problems — Certifying that matrices are PSD
v1.3 research notesGiven 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...
10 Lectures and 42 Open Problems — The Paley ETF Conjecture
v1.3 research notesDoes the Paley Equiangular tight frame satisfy the Restricted Isometry Property pass the square root bottleneck? (even by logarithmic factors?)....
10 Lectures and 42 Open Problems — Gilbert-Varshamov bound
v1.3 research notesExplicit deterministic constructions of codes achieving the GV bound Is the GV bound tight?...
10 Lectures and 42 Open Problems — Boolean classification and annulus conjecture
v1.3 research notesProve or disprove: $R_A(\alpha n,\beta n,n)=\alpha+(1-\alpha)R_A(1,\beta n,(1-\alpha)n)+o(1)$....
10 Lectures and 42 Open Problems — The Deletion Channel
v1.3 research notesWhat are the asymptotics of $\mathcal{D}\left(n;\frac12\right)$ ? \item An interesting aspect of the Deletion Channel is that different messages may h...
10 Lectures and 42 Open Problems — Maximum and minimum bisections on random regular graphs
v1.3 research notesGiven 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...
10 Lectures and 42 Open Problems — Sharp tightness of the Angular Synchronization SDP
v1.3 research notesIs the SDP for angular synchronization tight (with high probability) for noise levels $\sigma$ essentially until the solution of angular synchronizati...
10 Lectures and 42 Open Problems — Tightness of the Multireference Alignment SDP
v1.3 research notesFor which levels of noise is the SDP for Multireference Alignment tight?...
10 Lectures and 42 Open Problems — Consistency and sample complexity of Multireference Alignment
v1.3 research notesIs the Maximum likelihood for Multireference Alignment consistent? (after fixing the power spectrum) What is the sample complexity of the Multireferen...
Dynamic Planar Nearest Neighbors
v1.3 research notesIs 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...
3.10 (Futer, Schleimer) — A practical 3-manifold homeomorphism algorithm
v1.3 research notesIs there a practical algorithm to test whether a pair of $3$-manifolds are homeomorphic?...
8.4 (Schleimer) — Detecting reducible Heegaard splittings
v1.3 research notesIs there an algorithm to detect whether a Heegaard splitting is reducible and, if so, find a reducing curve?...