Komplexität und Logik Seminar SoSe 2020

Modultitel (deutsch)

Komplexität und Logik Seminar

Modultitel (englisch)

Complexity and Logic

Modul-Verantwortliche/r

Olaf Beyersdorff

Zusammensetzung des Moduls / Lehrformen  (V, Ü, S, Praktikum, …)

2 S

Leistungspunkte (ECTS credits)

2 LP

Inhalte

Seminar zu wechselnden aktuellen Themen der Logik in der Informatik

Typische Themen sind:

  • Verschiedene Logiken: Aussagenlogik, erststufige Logik, QBF, modale, intuitionistische Logiken etc.
  • Komplexität dieser Logiken
  • Beweiskalküle der Logiken
  • Algorithmische Aspekte
  • SAT- und QBF Solver
  • Beweiskomplexität
  • Berechnungskomplexität
  • Algebraische Beweissysteme
 
Termine

Di., 16:00 bis 18:00 Uhr


Vortragsplan für das Semester

The seminar will be held online in English.
The tentative list of talks is as follows:
Olaf Beyersdorff, Introduction
David Sherratt, Circular Proofs and Resolution
Benjamin Böhm, Polynomial Calculus and Gröbner Bases
Matthias Döpmann, Lower Bounds via Games for QBF
Joshua Blinkhorn, Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution
Tomáš Peitl, DQBF
Tiemo Schröder, Programming Languages/Proofs are Programs