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

Institutionen för datavetenskap

Forskningsoutput: Tidskriftsbidrag › Artikel i vetenskaplig tidskrift › Peer review

Sammanfattning

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.

Originalspråk	engelska
Artikelnummer	23
Sidor (från-till)	1-26
Tidskrift	Journal of the ACM
Volym	68
Nummer	4
DOI	https://doi.org/10.1145/3449352
Status	Published - 2021 aug.

Ämnesklassifikation (UKÄ)

Datavetenskap (datalogi)
Diskret matematik

Tillgång till dokument

10.1145/3449352

Citera det här

@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

Sammanfattning

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Citera det här