10 problems

Let $p$ be odd and fix an integer $\ell\in[\lfloor p/2\rfloor,n-\lceil p/2\rceil]$. For $S\subseteq[n]$ with $|S|=\ell$ and $T\subseteq[n]$ with $|T|=\ell+1$, define the rectangula…

Fix an integer $p$ and let $\ell$ be constant independently of $n$. Log-free performance conjecture. There exists a constant $c_p(\ell)>0$, with $c_p(\ell)\to 0$ as $\ell\to\infty$…

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…

Powered adjacency recovery conjecture. Let $a,b\geq 0$ satisfy $(a-b)^2>2(a+b)$, let $r=\Theta(\sqrt{\log n})$, and let $G\sim\mathrm{SBM}(n,a,b)$. If $w$ is the eigenvector of…

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 spectral recovery conjecture. Choose $p$ and $Q$ such that vertices from every community have the same expected degree and there is an efficient algorithm that solves weak…

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…