[Proof Complexity] Olaf Beyersdorff seminar on Monday

[thapen]

Dear colleagues,

Olaf Beyersdorff will give a proof complexity talk in our online logic 
seminar on Monday, at 15:30 Prague time - see the announcement below.

To join go to
https://cesnet.zoom.us/j/472648284?pwd=ZTlxeHhqWlltR1AzZC9CTHgzZ2tRZz09
Passcode: 017107 (if required)

Best,

Neil
-----

Quantified Boolean formulas: proof systems, circuit complexity, and 
solving

Olaf Beyersdorff, Friedrich Schiller University Jena

Monday, 11. January 2021 - 15:30 to 17:00

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. The talk will also cover 
the relations between QBF resolution and QCDCL solving algorithms. 
Modelling QCDCL as proof systems we show that QCDCL and Q-Resolution are 
incomparable.

This talk is based on two recent papers, joint with Joshua Blinkhorn and 
Meena Mahajan (LICS'20) and with Benjamin Boehm (ITCS'21).