[Proof Complexity] Olaf Beyersdorff seminar on Monday
thapen
thapen at math.cas.cz
Thu Jan 7 11:27:38 CET 2021
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).
More information about the Proof-Complexity
mailing list