Clique is hard on average for regular resolution

Link identifier archive #link-archive-thumb-soap-60850
Clique is hard on average for regular resolution
Venerdì 19 giugno 2020 alle ore 11:30, il prof. Massimo Lauria dell'Università di Roma La Sapienza, presenterà il seminario di Logica e Informatica Teorica dal titolo "Clique is hard on average for regular resolution".


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 o cliccare sul seguente link Link identifier #identifier__111751-2Teams meeting
Link identifier #identifier__5859-1Link identifier #identifier__83645-2Link identifier #identifier__59772-3Link identifier #identifier__88269-4

This post is also available in: Link identifier #identifier__157323-5enEng