Clique is hard on average for regular resolution
(2018) 50th Annual ACM Symposium on Theory of Computing, STOC 2018 In Proceedings of the Annual ACM Symposium on Theory of Computing p.646-659- 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/81833e35-16cc-4748-8203-8e7fc02bf840
- author
- Atserias, Albert ; Bonacina, Ilario ; De Rezende, Susanna F. LU ; Lauria, Massimo ; Nordström, Jakob LU and Razborov, Alexander
- publishing date
- 2018-06-20
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Erdős-Rényi random graphs, K-clique, Proof complexity, Regular resolution
- host publication
- STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
- series title
- Proceedings of the Annual ACM Symposium on Theory of Computing
- editor
- Henzinger, Monika ; Kempe, David and Diakonikolas, Ilias
- pages
- 14 pages
- publisher
- Association for Computing Machinery (ACM)
- conference name
- 50th Annual ACM Symposium on Theory of Computing, STOC 2018
- conference location
- Los Angeles, United States
- conference dates
- 2018-06-25 - 2018-06-29
- external identifiers
-
- scopus:85043471352
- ISSN
- 0737-8017
- ISBN
- 9781450355599
- DOI
- 10.1145/3188745.3188856
- language
- English
- LU publication?
- no
- id
- 81833e35-16cc-4748-8203-8e7fc02bf840
- date added to LUP
- 2020-12-18 22:19:28
- date last changed
- 2022-04-26 22:47:26
@inproceedings{81833e35-16cc-4748-8203-8e7fc02bf840, abstract = {{<p>We prove that for k ≪ <sup>4</sup> n regular resolution requires length n<sup>Ω</sup>(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<sup>Ω</sup>(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.</p>}}, author = {{Atserias, Albert and Bonacina, Ilario and De Rezende, Susanna F. and Lauria, Massimo and Nordström, Jakob and Razborov, Alexander}}, booktitle = {{STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing}}, editor = {{Henzinger, Monika and Kempe, David and Diakonikolas, Ilias}}, isbn = {{9781450355599}}, issn = {{0737-8017}}, keywords = {{Erdős-Rényi random graphs; K-clique; Proof complexity; Regular resolution}}, language = {{eng}}, month = {{06}}, pages = {{646--659}}, publisher = {{Association for Computing Machinery (ACM)}}, series = {{Proceedings of the Annual ACM Symposium on Theory of Computing}}, title = {{Clique is hard on average for regular resolution}}, url = {{http://dx.doi.org/10.1145/3188745.3188856}}, doi = {{10.1145/3188745.3188856}}, year = {{2018}}, }