Clique Is Hard on Average for Regular Resolution

12/17/2020
by   Albert Atserias, et al.
0

We prove that for k ≪√(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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset