Clique Is Hard on Average for Regular Resolution

Albert Atserias; Ilario Bonacina; Susanna F. De Rezende; Massimo Lauria; Jakob Nordström; Alexander Razborov

doi:10.1145/3449352

Clique Is Hard on Average for Regular Resolution

Albert Atserias, Ilario Bonacina, Susanna F. De Rezende, Massimo Lauria, Jakob Nordström, Alexander Razborov

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	23
Pages (from-to)	1-26
Journal	Journal of the ACM
Volume	68
Issue number	4
DOIs	https://doi.org/10.1145/3449352
Publication status	Published - 2021 Aug

Subject classification (UKÄ)

Computer Sciences
Discrete Mathematics

Free keywords

average complexity
clique
Resolution

Access to Document

10.1145/3449352

Cite this

@article{1ab84d2d67a049fd898d0a9a160e2f39,

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{\AA}'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 = "average complexity, clique, Resolution",

author = "Albert Atserias and Ilario Bonacina and {De Rezende}, {Susanna F.} and Massimo Lauria and Jakob Nordstr{\"o}m and Alexander Razborov",

year = "2021",

month = aug,

doi = "10.1145/3449352",

language = "English",

volume = "68",

pages = "1--26",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Clique Is Hard on Average for Regular Resolution

AU - Atserias, Albert

AU - Bonacina, Ilario

AU - De Rezende, Susanna F.

AU - Lauria, Massimo

AU - Nordström, Jakob

AU - Razborov, Alexander

PY - 2021/8

Y1 - 2021/8

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 - average complexity

KW - clique

KW - Resolution

U2 - 10.1145/3449352

DO - 10.1145/3449352

M3 - Article

SN - 0004-5411

VL - 68

SP - 1

EP - 26

JO - Journal of the ACM

JF - Journal of the ACM

IS - 4

M1 - 23

ER -

Clique Is Hard on Average for Regular Resolution

Abstract

Subject classification (UKÄ)

Free keywords

Access to Document

Fingerprint

Cite this