50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Announcements 2010


  • Wir gratulieren ganz herzlich Team Lübeck 2 zur Bronzemedaille und Platz 10, sowie Team Lübeck 1 zum 32. Platz unter 67 teilnehmenden Teams.



  • Teamcoach PD Dr. M. Liskiewicz mit Team Lübeck 1 und 2


    Übergabe der Bronzemedaille an das Team Lübeck 2


    Team Lübeck 2: Ingmar Kaden, Sebastian Hungerecker, Martin Schuster


    Team Lübeck 1: Philipp Harms, Fabian Guth, Alexander Idelberger



  • Die k-Means-Methode ist einer der populärsten Clustering-Algorithmen. Der Hauptgrund dafür ist ihre hervorragende Laufzeit in der Praxis. Dem gegenüber steht eine exponentielle Worst-Case-Laufzeit.


    Wir schließen diese Lücke zwischen Theorie und Praxis mittels Smoothed Analysis: Ein Adversary wählt Datenpunkte, die dann anhand von Gaußverteilungen leicht verrauscht werden. Dies modelliert beispielsweise Messfehler und zerstört pathologische Worst-Case-Instanzen. Die Smoothed-Laufzeit ist die maximale erwartete Laufzeit, die der Adversary erreichen kann.


    Wir zeigen, dass die Smoothed-Laufzeit der k-Means-Methode polynomiell in der Anzahl der Datenpunkte und dem Kehrwert der Standardabweichung der Störung ist. Anschließend analysieren wir die k-Means-Methode für allgemeinere Distanzmaße, so genannte Bregman-Divergenzen. Diese umfassen Mahalanobis- Distanzen und Kullback-Leibler-Divergenz.

  • ACM German Collegiate Programming Contest GCPC 2010

    Saturday, 12.06.2010 10-15h

  • Complexity Theory Meeting

    Monday, 22.02.10 from 12.30 to 17.20

    Am 22.02.10 von 12.30 Uhr bis 17.20 Uhr findet ein Forschungsseminar zur Komplexitätstheorie im Institut für Theoretische Informatik statt. Interessierte Studierende und Mitarbeiter anderer Institute sind dazu herzlich eingeladen. (Kontakt: Ilka Schnoor, Michael Elberfeld)

    Planung

    Uhrzeit Vortragende und Themen
    12.30 Eintreffen
    12.40 Oleg Verbitsky (HU Berlin)
    A LOGSPACE Isomorphism Test for Interval Graphs
    Zusammenfassung anzeigen
    13.30 Mittagspause
    14.45 Peter Lohmann, Heribert Vollmer (Uni Hannover)
    Complexity Results for Modal Dependence Logic
    Zusammenfassung anzeigen
    15.30 Michael Elberfeld (Uni Lübeck)
    Computing Tree Decompositions of Bounded Width in Logspace
    Zusammenfassung anzeigen
    16.15 Kaffeepause
    16.35 Martin Mundhenk (Uni Jena)
    Formelauswertung für intuitionistische Logik
    Zusammenfassung anzeigen
    17.20 Ende