Title: Planted Cliques and Local Partitioning in Massive Graphs

Abstract: The "planted clique" problem is to identify a clique on k
randomly chosen nodes that is "planted" in a random graph G(n,1/2) on
n nodes. Currently, such cliques can be found in polynomial time only
if k exceeds the square root of n. The seminal paper on this topic, by
Alon, Krivelevich and Sudakov, used spectral methods. I will present
an algorithm (joint work with O. Gurel-Gurevich and Y. Dekel) that
does this in time n^2 with high probability, inspired by earlier work
of Feige and Ron.  Detecting smaller cliques remains a tantalizing
open problem.  The second part of the talk concerns local
partitioning: A local partitioning algorithm in a large graph finds a
sparse cut near a given target node by examining only a small part of
the entire graph.  I will describe the "evolving set" partitioning
algorithm (STOC 2009), which is joint work with Reid Andersen and is
based on earlier work with Ben Morris on mixing times. Recently, this
algorithm was refined by Oveis-Gharan and Trevisan.