9 problems

The Planted Clique problem asks whether an Erdős–Rényi graph on $n$ vertices contains a planted clique of size $k$. Planted Clique conjecture. There is no polynomial-time algorithm…

Let an SST matrix be a matrix satisfying the strong stochastic transitivity condition, and consider its estimation under the Frobenius norm. Statistical-computational gap conjectur…

Computational lower-bound conjecture. No polynomial-time algorithm can recover the latent subspace with $\Theta_d(d)$ samples for general link functions $ud$.

Let $p\in(0,1)$ be constant. For each $n$, let $A_n:G_n\to\{0,1\}$ be a randomized polynomial-time algorithm, and let $k_n$ be a sequence of positive integers satisfying … For the…

Statistical–computational gap conjecture. There is a fundamental gap between statistical optimality and computational efficiency for noisy disordered matrix reordering: although st…

The subgraph ensemble consists of a null and a planted model with hidden structure $\Gamma_k$, and one may ask for polynomial-time algorithms solving the corresponding detection an…

Let $G$ be a random graph in the planted clique detection problem, with $N$ vertices and planted clique size $\kappa$. A polynomial-time test is an algorithm whose running time is…

Let $K$ signals be observed through averaged mean, power-spectrum, and bispectrum measurements, and let $L$ denote the signal length. Statistical-computational gap conjecture. The…

Let the unknown matrix belong to the class of strong stochastic transitivity (SST) matrices, and measure estimation error in the rate used for the SST estimation problem. Consider…