2 problems

Computational-threshold conjecture. For random graphs of logarithmic average degree, $\rho^2=\alpha$ is the computational threshold for graph matching.

Computational-threshold conjecture. When $s^2<\alpha$, an information-computation gap exists for correlated Erdős–Rényi graphs.