BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

QBF Proof Complexity Beyersdorff, Olaf


This talk will give an overview of the relatively young field of QBF proof complexity, explaining QBF proof systems (including QBF resolution, Frege and beyond). We will explore the simulation order of different QBF calculi and how they correspond to ideas in QBF solving.

A particular focus of the talk will be on lower bound techniques for QBF systems and in particular new ideas, which do not just lift propositional hardness, but exploit hardness stemming from quantifier dependencies.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International