I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ?
A recent paper by Feldman, Perkins and Vempala builds the connection between Statistical Algorithms and Convex Relaxations by showing that for detecting planted k-CSPs, lower bounds on the complexity of Statistical Algorithms can be translated to lower bounds on the dimension of canonical convex relaxations.
I was wondering if a similar thing can be said about Planted Clique lower bounds for Statistical Algorithms (which were proven here). In particular what kind (if any) of lower bounds on Convex Relaxations do these imply?
