PROBLEM DEFINITION A concrete version of the problem is to distinguish between the following two cases. A random graph from $G(n,1/)$ and a random graph with a size planted subgraph which by itself is $G(,1/n^{¼ + \epsilon})$. Note that if we look at $$ size subgraph in $G(n,1/)$. It has average degree 1 whereas $G(,1/n^{¼ + \epsilon})$ has average degree n¼ − ϵ. CONVEX RELAXATIONS Indeed one can model the problem as trying to find the densest subgraph of size $$. I.e. Maximise xi − xj in 0-1 polytope of all strings of size upto $$. Some Questions here - Can we reason about the extension complexity of the above polytope? We argued that it is of course less than $n^$. By the same Sherali Adams type idea. - What about Sherali Adams lower bounds for distinguishing these two cases? - Can Sherali Adams lower bounds be translated to LP lower bounds a la CLRS. Note that the good part above is that it is free from instance dependent constraints in the LP itself. - One can also look at SOS versions of the above question ? What is the SOS complexity of planted dense subgraphs ? - Can such a version be converted into proof of an SDP lower bound ? SOME OTHER THINGS Another very unrelated question in terms of SOS lower bounds is Stochastic Block Models Can one show an SOS lower bound for the recovery threshold in Stochastic Block Models? What’s even the right formulation of the question actually ?