Warning: Table './church/sessions' is marked as crashed and last (automatic?) repair failed
query: SELECT sid FROM sessions WHERE sid = 'tbhdhut9sd0s8ljku80pn311g2' in /var/www/church/includes/database.mysql.inc on line 121 Gruppo di Logica e Geometria della Cognizione
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".
Abstract
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
Warning: Can't find file: 'watchdog' (errno: 2)
query: INSERT INTO watchdog (uid, type, message, severity, link, location, referer, hostname, timestamp) VALUES (0, 'php', 'Table './church/sessions' is marked as crashed and last (automatic?) repair failed\nquery: SELECT sid FROM sessions WHERE sid = 'tbhdhut9sd0s8ljku80pn311g2' in /var/www/church/includes/database.mysql.inc on line 121.', 2, '', 'http://logica.uniroma3.it/calendario/2020/6/19', '', '216.73.216.58', 1751612316) in /var/www/church/includes/database.mysql.inc on line 121
Warning: Can't find file: 'watchdog' (errno: 2)
query: INSERT INTO watchdog (uid, type, message, severity, link, location, referer, hostname, timestamp) VALUES (0, 'php', 'Table './church/sessions' is marked as crashed and last (automatic?) repair failed\nquery: INSERT INTO sessions (sid, uid, cache, hostname, session, timestamp) VALUES ('tbhdhut9sd0s8ljku80pn311g2', 0, 0, '216.73.216.58', 'calendar_year|i:2020;calendar_mon|i:6;', 1751612316) in /var/www/church/includes/database.mysql.inc on line 121.', 2, '', 'http://logica.uniroma3.it/calendario/2020/6/19', '', '216.73.216.58', 1751612316) in /var/www/church/includes/database.mysql.inc on line 121
