Warning: Table './church/sessions' is marked as crashed and last (automatic?) repair failed query: SELECT sid FROM sessions WHERE sid = 'jv5fcgj7rvv266epupi8ma4l90' in /var/www/church/includes/database.mysql.inc on line 121
Gruppo di Logica e Geometria della Cognizione
Year | Month | Week | Day
« prevVenerdì, Giugno 19 2020next »
Key 1

Clique is hard on average for regular resolution

Speaker:
Massimo Lauria
Quando:
19/06/2020 - 11:30
Dove:
videoconferenza online
Abstract

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 = 'jv5fcgj7rvv266epupi8ma4l90' in /var/www/church/includes/database.mysql.inc on line 121.', 2, '', 'http://logica.uniroma3.it/calendario/2020/06/19', '', '216.73.216.58', 1751592125) 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 ('jv5fcgj7rvv266epupi8ma4l90', 0, 0, '216.73.216.58', 'calendar_year|i:2020;calendar_mon|i:6;', 1751592125) in /var/www/church/includes/database.mysql.inc on line 121.', 2, '', 'http://logica.uniroma3.it/calendario/2020/06/19', '', '216.73.216.58', 1751592125) in /var/www/church/includes/database.mysql.inc on line 121