Standard
Clique is hard on average for regular resolution. / Atserias, Albert; Lauria, Massimo; Bonacina, Ilario; Nordström, Jakob; De Rezende, Susanna F.; Razborov, Alexander.
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Monika Henzinger; David Kempe; Ilias Diakonikolas. ACM Association for Computing Machinery, 2018. p. 646-659 (Proceedings of the Annual ACM Symposium on Theory of Computing).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Atserias, A, Lauria, M, Bonacina, I
, Nordström, J, De Rezende, SF & Razborov, A 2018,
Clique is hard on average for regular resolution. in M Henzinger, D Kempe & I Diakonikolas (eds),
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ACM Association for Computing Machinery, Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 646-659, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States,
25/06/2018.
https://doi.org/10.1145/3188745.3188856APA
Atserias, A., Lauria, M., Bonacina, I.
, Nordström, J., De Rezende, S. F., & Razborov, A. (2018).
Clique is hard on average for regular resolution. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.),
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 646-659). ACM Association for Computing Machinery. Proceedings of the Annual ACM Symposium on Theory of Computing
https://doi.org/10.1145/3188745.3188856Vancouver
Atserias A, Lauria M, Bonacina I
, Nordström J, De Rezende SF, Razborov A.
Clique is hard on average for regular resolution. In Henzinger M, Kempe D, Diakonikolas I, editors, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ACM Association for Computing Machinery. 2018. p. 646-659. (Proceedings of the Annual ACM Symposium on Theory of Computing).
https://doi.org/10.1145/3188745.3188856Author
Atserias, Albert ; Lauria, Massimo ; Bonacina, Ilario ; Nordström, Jakob ; De Rezende, Susanna F. ; Razborov, Alexander. / Clique is hard on average for regular resolution. STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. editor / Monika Henzinger ; David Kempe ; Ilias Diakonikolas. ACM Association for Computing Machinery, 2018. pp. 646-659 (Proceedings of the Annual ACM Symposium on Theory of Computing).
Bibtex
@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",
}
RIS
TY - GEN
T1 - Clique is hard on average for regular resolution
AU - Atserias, Albert
AU - Lauria, Massimo
AU - Bonacina, Ilario
AU - Nordström, Jakob
AU - De Rezende, Susanna F.
AU - Razborov, Alexander
PY - 2018/6/20
Y1 - 2018/6/20
N2 - 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.
AB - 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.
KW - Erdős-Rényi random graphs
KW - K-clique
KW - Proof complexity
KW - Regular resolution
UR - http://www.scopus.com/inward/record.url?scp=85043471352&partnerID=8YFLogxK
U2 - 10.1145/3188745.3188856
DO - 10.1145/3188745.3188856
M3 - Article in proceedings
AN - SCOPUS:85043471352
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 646
EP - 659
BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Henzinger, Monika
A2 - Kempe, David
A2 - Diakonikolas, Ilias
PB - ACM Association for Computing Machinery
T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018
Y2 - 25 June 2018 through 29 June 2018
ER -
