The ACO Seminar (2013–2014)

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² 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).)