Clique Is Hard on Average for Regular Resolution

Abstract

We prove that for k ≪ 4√ n regular resolution 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.