Department Seminar Series

Semi-Algebraic Proof Systems for QBF

19th August 2025, 13:00 add to calender
Meena Mahajan
The Institute of Mathematical Sciences, Chennai

Abstract

We 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.

This is joint work with Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, and Luc Spachmann.


add to calender (including abstract)

Biography

Meena Mahajan is a professor at The Institute of Mathematical Sciences, HBNI, Chennai, India. Her interests span most of theoretical computer science. Her research focusses primarily on understanding the limits of efficient computation, and encompasses many aspects of complexity theory, including Boolean function complexity, algebraic circuits, and proof complexity.

Additional Materials