BIRS Workshop Lecture Videos
Characterising QBF Hardness via Circuit Complexity Beyersdorff, Olaf
This talk will start with an overview of the relatively young field of QBF proof complexity, explaining QBF proof systems (including QBF resolution) and an assessment of which lower bound techniques are available for QBF proof systems. In the main part of the talk, I will explain hardness characterisations for QBF proof systems in terms of circuit complexity, yielding very direct connections between circuit lower bounds and QBF proof system lower bounds.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International