Before revision:  ( iii) a rigorous polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the planted signal significantly better than a random guess would . The rigorous algorithms are based on the spectra of matrices that arise as the derivatives of the belief propagation update rule. An interesting unanswered question raised is that of obtaining evidence of computational hardness for convex relaxations whenever hardness is predicted by the cavity method .
After revision:  ( iii) a rigorous polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the planted signal significantly better than a random guess would .