I will talk about a convex relaxation of this problem, and explain why it doesn’t seem to do much better than standard methods in the usual case, where G is thought of as an Erdos-Renyi graph. (More or less: you can find H if |H| is bigger than the square root of N, otherwise, forget it.) However, the standard methods for planted clique have trouble when G is drawn from a more general, less homogeneous, more realistic random graph model (of course I have in mind the “graphons” I talked about in my last SILO talk) and it seems likely to me that the convex relaxation will be more robust to this change, and will still find cliques of square-root size.
A central theme will be the following theorem in graph theory: whenever you come up with an idea about graph theory, Lovasz has already thought of it.
Discovery Building, Orchard View Room