Seminari del Dipartimento

 

Logica e Informatica Teorica

Clique is hard on average for regular resolution

Massimo Lauria


19-06-2020 - 11:30
modalitĂ  telematica

 

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 vitomichele.abrusci@uniroma3.it 

o cliccare sul seguente link Teams meeting
https://teams.microsoft.com/dl/launcher/launcher.html?url=%2f_%23%2fl%2fmeetup-join%2f19%3a388bb369590943489346c5edc8bb7b83%40thread.tacv2%2f1590962418579%3fcontext%3d%257B%2522Tid%2522%3a%2522ffb4df68-f464-458c-a546-00fb3af66f6a%2522%2c%2522Oid%2522%3a%252211647586-a255-4c31-b3ea-1a3032a3b0a8%2522%257D%26anon%3dtrue&type=meetup-join&deeplinkId=2dcc115c-37a1-4a8c-b13b-1dccabb63671&directDl=true&msLaunch=true&enableMobilePage=true&suppressPrompt=true
org: PEDICINI Marco

Copyright© 2014 Dipartimento di Matematica e Fisica