Instituts-Logo Logik in der Informatik
Prof. Dr. Nicole Schweikardt
Humboldt-Logo

Seminar Aktuelle Themen in Logik und Komplexität

Wintersemester 2015/16

Aktuelles   Einführung    Ort und Zeit    Vorträge    Vortragsthemen   Spielregeln


Aktuelles


Einführung

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen im Bereich Logik und Komplexität erarbeitet.

Ziele sind das Kennenlernen neuer Forschungsergebnisse, das Verstehen wissenschaftlicher Originaltexte, die Fähigkeit zur Einordnung der Inhalte und Beweistechniken, sowie deren Wiedergabe in eigener Darstellung in einem begrenzten Zeitrahmen.

Das Seminar richtet sich an fortgeschrittene Studierende in einem Diplom- oder Masterstudiengang, die sich im Bereich Logik und Komplexität spezialisieren wollen. Die Teilnahme am Seminar setzt Kenntnisse, die in der Vorlesung "Logik und Komplexität" vermittelt werden, voraus.


Ort und Zeit

Zeit und Raum
Mittwochs, 15:15-17:00 Uhr im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.408
 
Veranstalter/in
Prof. Dr. Nicole Schweikardt und Dr. Christoph Berkholz

Vorträge

28.10. Christoph Berkholz Die Frage nach einer Logik für PTIME.
Basierend auf Gurevich "Logik and the Challenge of Computer Science" (1988) und Nash, Remmel, Vianu "PTIME Queries Revisited" (2005)
04.11. Nicole Schweikardt IFP+C: Fixpunktlogik mit Zähloperatoren.
Basierend auf "Abschnitt 2.4.3" von "Chapter 2: Background from Graph Theory and Logic" des Buchs Descriptive Complexity, Canonisation, and Definable Graph Structure Theory von Martin Grohe (Version: Nov 25, 2013) und auf der "Introduction" des Artikels Fixed-point definability and polynomial time on graphs with excluded minors von Martin Grohe (J. ACM 59(5):27 (2012))
11.11. Berit Grußien Transduktionen
18.11. Christoph Berkholz Untere Schranken an den Quantorenrang von k-Variablen Logik. Basierend auf einer noch unveröffentlichten Arbeit von C. Berkholz und J. Nordström.
25.11. 17:00 Lucas Heimberg Lokalität Teil I
02.12. 17:00 Lucas Heimberg Lokalität Teil II
09.12. Jens Keppeler Strombasierte Aufzählung von Anfrageergebnissen für Datenbanken von geringem Grad
16.12. kein Seminar
06.01. 17:00 Lucas Heimberg Lokalität Teil III: Eine untere Schranke für Hanf-Normalform.
13.01. Benjamin Hauskeller "An optimal lower bound on the number of variables for graph identifications" von J. Cai, M. Fürer und N. Immerman
20.01. kein Seminar
27.01. Denis Erfurt "Choiceless Computation and Symmetry" von B. Rossman
03.02. kein Seminar
10.02. Pascal Kunz "Choiceless Polynomial Time, Counting and Cai-Fürer-Immerman graphs" von A. Dawar, D. Richerby und B. Rossman

Mögliche Vortragsthemen

  1. An optimal construction of Hanf sentences von Benedikt Bollig und Dietrich Kuske. J. Applied Logic 10(2): 179-186 (2012)
    Zusätzliches Material: Appendix A der Arbeit An optimal Gaifman normal form construction for structures of bounded degree von Lucas Heimberg, Dietrich Kuske und Nicole Schweikardt (ausführliche Version einer bei LICS 2013 erschienenen Arbeit).

  2. Shrinking Games and Local Formulas von H. Jerome Keisler und Wafik Boulos Lotfallah. Ann. Pure Appl. Logic 128(1-3): 215-225 (2004)

  3. An existential locality theorem von Martin Grohe und Stefan Wöhrle. Ann. Pure Appl. Logic 129(1-3): 131-148 (2004)

  4. Faster decision of first-order graph properties von Ryan Williams. CSL-LICS 2014: 80:1-80:6
  5. An optimal lower bound on the number of variables for graph identifications von Jin-yi Cai, Martin Fürer und Neil Immerman. Combinatorica 12(4): 389-410 (1992)

  6. Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations von Martin Fürer. ICALP 2001: 322-333

  7. Choiceless Computation and Symmetry von Benjamin Rossman. Fields of Logic and Computation 2010: 565-580; Springer-Verlag
  8. Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs von Anuj Dawar, David Richerby und Benjamin Rossman. Ann. Pure Appl. Logic 152(1-3): 31-50 (2008)

  9. Choiceless Polynomial Time on Structures with Small Abelian Colour Classes von Faried Abu Zaid, Erich Grädel, Martin Grohe und Wied Pakusa. MFCS (1) 2014: 50-62 (als zusätzliches Material steht im Seminar eine noch unveröffentlichte Version mit ausführlichen Beweisen zur Verfügung)


Spielregeln

Zum Bestehen des Moduls sind nötig:
  1. Einen Vortrag zu einem der oben genannten Themen zu halten (Dauer ca. 60 Minuten, plus 10 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
  2. Anwesenheit an mind. 75% aller Vorträge und
  3. Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas: Länge ca 5 Seiten (mindestens 4, maximal 7), Layout wie in der Layout-Vorlage angegeben, Deadline: Ende des laufenden Semesters (also: 31.03.2016), 23:59 Uhr, als pdf-Datei per Email zu senden an Dr. Christoph Berkholz.

Last modified: 12.02.2016
Nicole Schweikardt