Clique Is Hard on Average for Regular Resolution

• We prove that for k << (4)root n regular resolution requires length n(Omega(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(Omega(k)) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

Ämnesord

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Nyckelord

Proof complexity

regular resolution

k-clique

Erdos-Renyi random graphs

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)