16 problems

Let $a>0$ be the average-degree parameter and let $\rho$ be the noise parameter, with $\rho=\epsilon$ and $\epsilon\in[0,1/2]$. In the sparse regime $p=a/n$, an estimator…

Vu–Abbe conjecture. Vanilla spectral algorithms are themselves good clustering algorithms for the stochastic block model.

Consider recovery of a planted sub-structure using a spectral algorithm or a semidefinite programming (SDP) algorithm, with the signal strength measured by the model's relevant sig…

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…

Random-walk failure conjecture. For all $a,b>0$, the algorithm that assigns vertices to communities by finding the $m$ dominant eigenvectors of the random walk matrix of the main c…

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…

Let a random vector have a non-Gaussian subspace whose marginals in every non-Gaussian direction are far from Gaussian in terms of moments, and consider the Reweighted PCA algorith…

Zhang et al.'s optimality conjecture. A spectral algorithm based on the non-backtracking operator should be optimal.