A local partitioning algorithm finds a “community” (i.e., a set of nodes with relatively few bonds to the outside) for a given node in a large graph, by examining only a small part of the entire graph. I will describe the “evolving set” partitioning algorithm, developed jointly with R. Andersen, based on earlier work with B. Morris. Recently, with P. Sousi and J. Steif, we found that evolving sets are especially effective for analyzing random walks on graphs that change in time. In the second part of the talk, I’ll present progress on the “planted clique” problem: locating a fully connected “clique” which is added to a typical dense graph on n nodes. Currently, cliques can be found in polynomial time only if their size exceeds the square root of $n$. The first technique to do this, analyzed by N. Alon et al, was spectral; in joint work with Y. Dekel and O. Gurel-Gurevich, we found a simpler algorithm that, with high probability, identifies the hidden clique in quadratic time $O(n^2)$. Whether smaller planted cliques (e.g., of size the cube root of $n$) can be detected in polynomial time, remains a tantalizing open problem.