Seminar über Computeralgebra, Kombinatorik und Komplexität

Prof. Dr. Peter Bürgisser

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