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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International