New Search

Export article

Clique Is Hard on Average for Regular Resolution

Albert Atserias, , Susanna F. De Rezende, Massimo Lauria, Jakob Nordström, Alexander Razborov

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.
Keywords: Resolution / average complexity / clique

Scifeed alert for new publications

Never miss any articles matching your research from any publisher
  • Get alerts for new papers matching your research
  • Find out the new papers from selected authors
  • Updated daily for 49'000+ journals and 6000+ publishers
  • Define your Scifeed now

Share this article

Click here to see the statistics on "Journal of the ACM" .
References (16)
    Back to Top Top