6 problems

Spectral meta-algorithm conjecture. For any $s$ and $r$ such that $\mathrm{GBM}(n,s,t)$ has a giant component, there exists $\delta>1/2$ such that the spectral meta-algorithm recov…

Subpolynomial-power failure conjecture. There exists $s_0>0$ such that, for all $m>0$, $s\geq s_0$, $t>0$, and $r=n^{o(1)}$, the algorithm that finds the second-largest-eigenvalue…

Powered adjacency conjecture. For all $m>0$, $s>0$, $t>0$, and $0<r'<1/2$, the algorithm that finds the eigenvector of $A^{(r'd)}$ with the second-largest eigenvalue and then divid…

Nonbacktracking failure conjecture. Computing the eigenvector of $B$ with the second-largest eigenvalue and dividing the vertices into those with above-median and below-median sums…

Powered adjacency conjecture. Let $s,t\geq 0$ and suppose $\mathrm{GBM}(n,s,t)$ has a giant component. Taking the second-largest eigenvector of $A^{(r)}$, with…

Weak recovery threshold conjecture. Let $s,t\geq 0$ and suppose $\mathrm{GBM}(n,s,t)$ has a giant component. Weak recovery is efficiently solvable in $\mathrm{GBM}(n,s,t)$ if and o…