Clique is Hard on Average for Regular Resolution

Ilario Bonacina

Deciding whether a graph G with n vertices has a k-clique is one of the most basic computational problems on graphs. 
In this talk we show that certifying k-clique-freeness of Erdos-Renyi random graphs is hard for regular resolution. 
More precisely we show that, for k<<\sqrt{n}, regular resolution asymptotically almost surely requires length n^{\Omega(k)} to 
establish that an Erdos-Renyi random graph (with appropriate edge density) does not contain a k-clique. This asymptotically optimal 
result implies unconditional lower bunds on the running time of several state-of-the-art algorithms used in practice.

This talk is based on on a joint work with A. Atserias, S. De Rezende, M. Lauria, J. Nordström and A. Razborov.