Susanna F. de Rezende: Clique Is Hard on Average for Regular Resolution

PRACTICALITIES

Lunch is served at 12:00 noon (register at tinyurl.com/TCS180411  at the latest Monday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

Deciding whether a graph has a k-clique is one of the most basic computational problems on graphs, and has been extensively studied in computational complexity theory ever since it appeared in Karp’s list of 21 NP-complete problems. In terms of upper bounds, the k-clique problem can clearly be solved in time roughly \(n^k\) simply by checking if any of the n many sets of vertices of size k forms a clique. The motivating problem behind this work is to determine the exact time complexity of the clique problem when k is given as a parameter.

In this talk we will show that for \(k <= n^{1/4}\) regular resolution asymptotically almost surely 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.

This is joint work with Albert Atserias, Ilario Bonacina, Massimo Lauria, Jakob Nordström and Alexander Razborov.

This presentation will also serve as Susanna's 80% PhD ladder seminar.