@inproceedings{669778b2d5ba4f39a4fad62a82ede1b3,
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 Massimo Lauria and Ilario Bonacina and Jakob Nordstr{\"o}m and {De Rezende}, {Susanna F.} 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 = "ACM Association for Computing Machinery",
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",
note = "50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",
}