Clique Is Hard on Average for Regular Resolution
Atserias, Albert ; Bonacina, Ilario ; De Rezende, Susanna F. LU
; Lauria, Massimo
; Nordström, Jakob
LU
and Razborov, Alexander
(2021)
In Journal of the ACM
68(4).
p.1-26
- 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/1ab84d2d-67a0-49fd-898d-0a9a160e2f39
- author
- Atserias, Albert
; Bonacina, Ilario
; De Rezende, Susanna F.
LU
; Lauria, Massimo
; Nordström, Jakob
LU
and Razborov, Alexander
- organization
- publishing date
- 2021-08
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- average complexity, clique, Resolution
- in
- Journal of the ACM
- volume
- 68
- issue
- 4
- article number
- 23
- pages
- 1 - 26
- publisher
- Association for Computing Machinery (ACM)
- external identifiers
-
- scopus:85122582849
- ISSN
- 0004-5411
- DOI
- 10.1145/3449352
- language
- English
- LU publication?
- yes
- id
- 1ab84d2d-67a0-49fd-898d-0a9a160e2f39
- date added to LUP
- 2021-12-17 13:08:06
- date last changed
- 2025-10-14 11:48:23
@article{1ab84d2d-67a0-49fd-898d-0a9a160e2f39,
abstract = {{<p>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. </p>}},
author = {{Atserias, Albert and Bonacina, Ilario and De Rezende, Susanna F. and Lauria, Massimo and Nordström, Jakob and Razborov, Alexander}},
issn = {{0004-5411}},
keywords = {{average complexity; clique; Resolution}},
language = {{eng}},
number = {{4}},
pages = {{1--26}},
publisher = {{Association for Computing Machinery (ACM)}},
series = {{Journal of the ACM}},
title = {{Clique Is Hard on Average for Regular Resolution}},
url = {{http://dx.doi.org/10.1145/3449352}},
doi = {{10.1145/3449352}},
volume = {{68}},
year = {{2021}},
}