Paper Info
Title
Clique is hard on average for regular resolution.
Abstract
We prove that for k ≪ n1/4 regular resolution requires length nΩ(k) to establish that an Erdos-Renyi 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.
Year
DOI
Venue
2018
10.1145/3188745.3188856
STOC '18: Symposium on Theory of Computing Los Angeles CA USA June, 2018
Keywords
Field
DocType
Proof complexity,regular resolution,k-clique,Erdos-Renyi random graphs
Graph,Discrete mathematics,Combinatorics,Exponent,Multiplicative function,Clique,Computer science,Upper and lower bounds,Edge density,Proof complexity
Conference
ISSN
ISBN
Citations 
0737-8017
978-1-4503-5559-9
6
PageRank 
References 
Authors
0.40
19
6
Name
Order
Citations
PageRank
Albert Atserias141932.76
Ilario Bonacina2586.49
Susanna F. de Rezende3134.35
Massimo Lauria412214.73
Jakob Nordström517721.76
Alexander A. Razborov671.09