Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Clique Is Hard on Average for Regular Resolution

Atserias, Albert ; Bonacina, Ilario ; De Rezende, Susanna F. LU orcid ; 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:
author
; ; ; ; and
organization
publishing date
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-04-04 14:47:06
@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}},
}