Student Probability Seminar

---

Large cliques in random graphs: geometry and computation

Speaker: Tim Kunisky, CIMS

Location: Warren Weaver Hall 1314

Date: Monday, February 25, 2019, 12:30 p.m.

Synopsis:

An Erdos-Renyi random graph with edge probability 1/2 on n vertices typically has a largest clique of size about 2 * log_2(n). On the other hand, given the graph, it seems hard to produce a clique of size any larger than log_2(n) with an efficient algorithm. We will discuss a few important works in the long history of attempts to understand this phenomenon, which give an explanation in terms of the geometry of “clique space.” Large cliques, it turns out, are “shattered” into clusters, where the cliques within a cluster overlap significantly, while the clusters themselves live in essentially disjoint regions of the graph. Making this precise in various ways, we will understand why naive Monte Carlo methods or other algorithms operating locally on the graph cannot move among these clusters to find out which ones contain the very largest cliques. We will also discuss how generalizations of this idea suggest a powerful and generic approach to understanding other instances of statistical-to-computational gaps in the theory of algorithms and machine learning.