Hidden Cliques in Large Graphs, Search Games and Kakeya Sets

In the first part of the talk, I'll discuss the "hidden clique" problem: locating a fully connected clique added to a random graph G(n,1/2) on n nodes. Currently, cliques can be found in polynomial time only if their size exceeds the square root of n. The seminal paper on this topic, by Alon, Krivelevich and Sudakov (1998), used spectral methods. With Y. Dekel and O. Gurel-Gurevich, we discovered a simple algorithm that locates such cliques in time n^2 with high probability, inspired by an idea of Feige and Ron (2010). Detecting smaller cliques remains a tantalizing open problem.

In the second (and independent) part of the talk, I'll describe a search game with a surprising geometric connection. A hunter and a rabbit move on an n-vertex graph without seeing each other until they meet. At each step, the hunter moves to a neighboring vertex or stays in place, while the rabbit is free to jump to any node. Thus they are engaged in a zero sum game, where the payoff is the capture time. We show that an optimal rabbit strategy for the cycle yields a Kakeya set: a plane set of zero area that contains a unit segment in every direction. Kakeya sets have been studied intensively in harmonic analysis since their discovery by Besicovitch (1919); their connection to search games is new and yields insights in both directions. This part is based on joint work with Y. Babichenko, R. Peretz, P. Sousi and P. Winkler (2013) and on earlier work by Adler et al (2003).


Yuval Peres is a Principal Researcher in the Theory group at Microsoft Research, Redmond. His research encompasses many areas of probability theory including random walks, mixing, Brownian motion, percolation, and random graphs, as well as connections with Ergodic Theory, PDE, Combinatorics, Fractals and Theoretical Computer Science; cf. http://research.microsoft.com/en-us/um/people/peres/ and http://arxiv.org/find/math/1/au:+Peres_Y/0/1/0/all/0/1

Markov chains and mixing (AMS) and on Brownian motion (Cambridge). Both books are freely accessible on his web page.

Faculty Host: Ryan O'Donnell


Subscribe to CSD-DLS