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 bounds 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.