Institute for Theoretical Computer Science

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 We construct in logarithmic space a modular decomposition tree for a given interval graph. Since the tree is definable in first-order logic, our construction is isomorphism-invariant. This reduces the isomorphism problem for interval graphs to the isomorphism problem for colored trees. Previously LOGSPACE isomorphism algorithms were known only for planar graphs and $k$-trees.
13.30	Mittagspause
14.45	Peter Lohmann, Heribert Vollmer (Uni Hannover) Complexity Results for Modal Dependence Logic Zusammenfassung anzeigen Modal dependence logic was introduced very recently by Väänänen. It enhances the basic modal language by an operator dep. For propositional variables p_1,...,p_n, dep(p_1,...,p_(n-1);p_n) intuitively states that the value of p_n only depends on those of p_1,...,p_(n-1). Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic exponential time. In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfibility for poor man's dependence logic, the language consisting of formulas built from literals and dependence atoms using conjunction, necessity and possibility (i.e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness. We also extend Väänänen's language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satistiability is complete for the second level of the polynomial hierarchy. In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster.
15.30	Michael Elberfeld (Uni Lübeck) Computing Tree Decompositions of Bounded Width in Logspace Zusammenfassung anzeigen We show how to construct tree decompositions of bounded width in deterministic logarithmic space. This opens up the possibility to construct Logspace algorithms for many problems on bounded tree width structures like, for example, 3-Colorability and Reachability. This is joint work with Andreas Jakoby and Till Tantau.
16.15	Kaffeepause
16.35	Martin Mundhenk (Uni Jena) Formelauswertung für intuitionistische Logik Zusammenfassung anzeigen The formula value problem is the problem to decide for a given formula and a given model whether the formula is satisfied by the model. Its complexity depends on the logic under consideration. E.g., for classical propositional logic the problem is NC1-complete [Buss, 1987], and for propositional hybrid logic it is PSPACE-complete [Franceschet et al, 2006]. We study the formula value problem for intuitionistic propositional logic IPC, superintuitionistic propositional logics, and their modal companions. We show that the formula value problem is P-complete for IPC and for the superintuitionistic logic KC (i.e. IPC plus the weak law of the excluded middle). Interestingly, for their modal companions S4 and S4.2 we also obtain P-completeness even if we consider formulas with one resp. two variables only. In contrast, for KC formulas with one variable only we obtain a much lower complexity, namely LOGDCFL as upper bound. For IPC formulas with one variable, we obtain AC1 as lower bound. This is a joint work with Felix Weiß.
17.20	Ende

Staff Overview

Professors

Secretary

Contact

Research assistants

Technical staff

Institute for Theoretical Computer Science

Events 2010

The Institute

Research

Courses and Studies

Quick links for

ACM German Collegiate Programming Contest GCPC 2010

Planung