BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T090950Z
UID:Seminar-dept-1284@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250819T130000
DTEND:20250819T140000
SUMMARY:School Seminar Series
DESCRIPTION:Meena Mahajan: Semi-Algebraic Proof Systems for QBF\n\nWe introduce new semi-algebraic proof systems for Quantified Boolean Formulas (QBF) analogous to the propositional systems Nullstellensatz, Sherali-Adams and Sum-of-Squares. We show how to transfer to this setting techniques both from the QBF literature (strategy extraction) and from propositional proof complexity (size-degree relations and pseudo-expectation). We obtain a number of strong QBF lower bounds and separations between these systems, even when disregarding propositional hardness.\n\n\n\nThis is joint work with Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, and Luc Spachmann.\n\n\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1284
LOCATION:
END:VEVENT
END:VCALENDAR