@inproceedings{81833e3516cc474882038e7fc02bf840,

title = "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{\H o}s–R{\'e}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 = "Erd{\H o}s-R{\'e}nyi random graphs, K-clique, Proof complexity, Regular resolution",

author = "Albert Atserias and Ilario Bonacina and {De Rezende}, {Susanna F.} and Massimo Lauria and Jakob Nordstr{\"o}m and Alexander Razborov",

year = "2018",

month = jun,

day = "20",

doi = "10.1145/3188745.3188856",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery (ACM)",

pages = "646--659",

editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",

booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

address = "United States",

note = "50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

}