The obvious running time to check whether a graph of n vertices has a clique of size k is roughly n^k. In this work we prove unconditionally that a large variety of state-of-the-art algorithms, even some that are widely used in practice, require running time n^Omega(k). More precisely we prove that for k << n^0.25 regular resolution proofs (i.e. read-once branching programs) have to be of size n^Omega(k) to establish that an Erdos-Rényi graph with appropriately chosen edge density does not contain a k-clique. We remark that these lower bounds do not depend on unproved assumptions like P vs NP, and apply to whatever algorithm that, on k-clique free graphs, produces a regular resolution proofs of such fact. The talk is based on a joint work appeared at STOC 2018, with: Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Jakob Nordström and Alexander A. Razborov.
Per partecipare al seminario, richiedere il link all’indirizzo email Link identifier #firstname.lastname@example.org o cliccare sul seguente link Link identifier #identifier__79304-2Teams meeting
This post is also available in: Link identifier #identifier__150780-5Eng