Clique is hard on average for regular resolution
04 Pubblicazione in atti di convegno
Atserias Albert, Lauria Massimo, Bonacina Ilario, Nordström Jakob, De Rezende Susanna F, Razborov Alexander
We prove that for k ≪4n 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.