BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260430T205705Z
UID:Seminar-dept-1269@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260526T130000
DTEND:20260526T140000
SUMMARY:School Seminar Series
DESCRIPTION:Fahad Panolan: Fine-Grained Bounds for Courcelle's Theorem\n\nCourcelle's theorem states that there exists an algorithm that takes as input an n-vertex graph G of treewidth at most t and an MSO formula phi,  and determines whether G satisfies phi f(phi,t) n. It is folklore that the function f contains a tower of exponentials whose height depends as a linear function of the number of quantifier alternations of the input formula  phi. A classic reduction of Frick and Grohe shows that, assuming the Exponential Time Hypothesis (ETH), the linear growth of the height of the tower is unavoidable. Nevertheless, there is still a huge gap between existing upper and lower bounds -- after all, there is quite a difference between a single exponential and a double exponential running time. In this talk, we discuss a fine-grained version of Courcelle's theorem with nearly ETH-tight dependence on the treewidth t and the quantifier structure of MSO formula phi. \n\n\n\nThis is joint work with Daniel Lokshtanov (University of California Santa Barbara) , Saket Saurabh (Institute of Mathematical Sciences), Jie Xue (New York University Shanghai), and Meirav Zehavi (Ben-Gurion University). \n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1269
LOCATION:
END:VEVENT
END:VCALENDAR