Abstract
Deciding whether a graph has a k-clique is one of the most basic computational problems on graphs, and has been extensively studied in computational complexity theory ever since it appeared in Karp’s list of 21 NP-complete problems. In terms of upper bounds, the k-clique problem can clearly be solved in time roughly n^k simply by checking if any of the sets of k vertices forms a clique. The motivating problem behind this work is to determine the exact time complexity of the clique problem when k is given as a parameter.
In this talk we will show that for any k <= n^{1/4} regular resolution asymptotically almost surely requires length n^{Ω(k)} to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n^{Ω(k)} lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
This is joint work with Albert Atserias, Ilario Bonacina, Massimo Lauria, Jakob Nordström and Alexander Razborov.