2020/12/17 by Atserias, Albert, Bonacina, Ilario, de Rezende, Susanna F. +3
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2012.09476
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.