2. ML vs. Bayes

ML vs. Bayes for spiked tensors
Problem 2.1.
[Andrea Montanari] Let $x_0$ be a uniformly random unit vector and observe $Y = \lambda x_0^{\otimes d} + W$ where $W$ is a symmetric tensor with $W_{i_1,\ldots,i_d} \sim \mathcal{N}(0,1/n)$ independently (up to symmetry). Let $\lambda^\mathrm{Bayes}$ and $\lambda^\mathrm{ML}$ denote the thresholds at which Bayesoptimal inference and maximumlikelihood estimation (respectively) achieve nontrivial correlation with the truth $x_0$. It is conjectured that $\lambda^\mathrm{Bayes} = \lambda^\mathrm{ML}$. These thresholds are also conjectured to be equal for the case $d = 2$ when $x_0$ has entries sampled i.i.d. from $\mathrm{Unif}\{\pm 1/\sqrt{n}\}$. 
ML vs. Bayes for SBM
Problem 2.2.
[Allan Sly] In the SBM and related models, are there regimes in which maximumlikelihood reconstruction does not achieve the optimal threshold? 
Separation in trees and graphs
Problem 2.3.
There are many connections between the SBM and the broadcast model in trees (which describes local neighborhoods). Are there questions (e.g. threshold for ML) for which the answer is different on trees than on graphs? 
Suboptimality of SDP
Problem 2.4.
Are there regimes (even in the 2block symmetric SBM) in which the SDP does not achieve the informationtheoretic threshold?
Cite this as: AimPL: Connecting communities via the block model, available at http://aimpl.org/blockmodel.