Es sollen wechselnde Themen aus den Bereichen Computeralgebra, Kombinatorik und Komplexitätstheorie besprochen werden. Teilnahme and diesem Seminar ist für Diplomanden und Doktoranden der AG Bürgisser verpflichtend.

Kriterium für den Scheinerwerb ist ein Vortrag mit Ausarbeitung.

Termin: Mittwoch, 14:00-15:30 im E0.206 (Beginn am 29. Oktober)

Themen

• Leitfähigkeit und schnelles Mischen von Markowketten auf regulären Graphen
  Andreas Kottmann, 29.10.2003
  Ausarbeitung: [ ps | pdf ]
  Literatur: Bóllobas, Modern Graph Theory, Kapitel
• Jansons Ungleichungen und Anwendungen auf Zufallsgraphen
  Ulrich Prior, 12.11.2003
  Ausarbeitung: [ ps | pdf ]
  Literatur:
• Pólyas Methode zur kombinatorischen Anzahlbestimmung
  Paul Kaufmann, 19.11.2003.
  Ausarbeitung: [ ps | pdf ]
  Literatur: Bóllobas, Modern Graph Theory, Kapitel
• Monotonicity Checking
  Marina Kyureghyan (Bielefeld), 10.12.2003
  Ort: F1.110 (Fürstenallee), gemeinsam mit Oberseminar Blömer/Meyer auf der Heide
  Zusammenfassung: [ ps | pdf ]
• Zur Komplexität der Berechnung der Anzahl Zusammenhangskomponenten semialgebraischer Mengen Teil 1
  Peter Scheiblechner, 14.01.2004.
  Literatur:
  P. Bürgisser, F. Cucker: Counting Complexity Classes for Numeric Computations I: Semilinear Sets
• Zur Komplexität der Berechnung der Anzahl Zusammenhangskomponenten semialgebraischer Mengen Teil 2
  Peter Scheiblechner, 21.01.2004.
  Literatur:
  P. Bürgisser, F. Cucker: Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets
• Keine Derandomisierung von RP ohne untere Schranken für Schaltkreiskomplexität
  Claudius Stern, 28.01.2004
  Zusammenfassung:
  In dem Vortrag wird ein Ergebnis von Valentine Kabanets und Russell Impagliazzo vorgestellt. Deren Arbeit befasst sich mit der Derandomisierung von Algorithmen in BPP bzw. in RP. Bisher ist bekannt, dass das Beweisen einer unteren Schranke für Schaltkreiskomplexität zu dem Schluss BPP=P führt. Hier wird gezeigt: Unter der Annahme, dass BPP=P ist (also die randomisierten Algorithmen in BPP derandomisiert werden können) folgt eine untere Schranke für Schaltkreiskomplexität (entweder boolsch oder arithmetisch).
  
  Ausarbeitung: [ ps | pdf ]
  Literatur: V. Kabanets, R. Impagliazzo: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds, STOC 03