Beweiskomplexität (Oberseminar)

In diesem Seminar werden verschiedene Paper und Masterarbeiten zum Thema Beweiskomplexität vorgestellt. Der Fokus liegt dabei überwiegend auf Resultaten aus dem SAT und QBF Bereich.

Interessenten mit thematisch passenden Vorträgen sind gern gesehen und können dazu bitte Herrn Professor Beyersdorff kontaktieren. 

Titel

Beweiskomplexität (Oberseminar)

Termine

Donnerstags, 16:15 Uhr

27.10.2022 Tim Hoffmann über „Lower Bounds for QBFs of Bounded Treewidth“
(Hecher, Fichte, 2022) - Grundidee

01.11.2022 Tim Hoffmann über „Lower Bounds for QBFs of Bounded Treewidth“
(Hecher, Fichte, 2022) - Details der Beweise

10.11.2022 Luc Spachmann über „A Model for Generating Random Quantified Boolean Formulas“
(Chen, Interian, 2005)

17.11.2022 Steffen Meier über seine Masterarbeit „Proof Calculi for the Contingencies of Propositional Logic“

24.11.2022 Benjamin Böhm - Einführung QDPLL

01.12.2022 Tim Hoffmann - Einführung Model Counting

05.01.2023 Steffen Meier - Sequenzkalküle vs. Resolution

12.01.2023 Benjamin Böhm - Paper zur Einführung von QCDCL