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 (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:
author
; ; ; ; and
publishing date
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}},
}