Forschungsinteressen des Lehrstuhls
Die Forschungsthemen des Lehrstuhls liegen vorwiegend in den Bereichen Komplexitätstheorie, Algorithmisches Lernen und Kryptografie. Die gegenwärtigen Interessen lassen sich entlang folgender Forschungslinien gliedern:
- Eine Reihe von algorithmischen Problemstellungen weisen auf Grund ihrer algebraischen Struktur andere Komplexitätseigenschaften auf als die üblichen kombinatorischen Probleme. So lassen sich beispielsweise das Graphisomorphieproblem oder das Faktorisierungproblem weder als effizient lösbar noch als NP-vollständig klassifizieren. Da diese Probleme sowohl aus theoretischer als auch aus praktischer Sicht eine bedeutende Rolle spielen, ist es wichtig, ihre strukturellen Eigenschaften (wie etwa Vollständigkeit oder Lowness für bestimmte Komplexitätsklassen) zu untersuchen.
- Ein verwandtes Forschungsthema ist durch die Frage motiviert, ob die Verwendung von Zufallsentscheidungen und/oder Interaktion mit einem Prover (oder Orakel) eine Steigerung der Effizienz von Algorithmen für bestimmte Probleme ermöglicht. Einen vielversprechenden Ansatz bietet die Erforschung der Beziehungen zwischen Komplexitätsklassen, die auf der Basis unterschiedlicher Berechnungsmodelle wie etwa Turingmaschinen, kombinatorische Schaltkreise oder interaktive Beweissysteme definiert sind. Innerhalb dieser Forschungsrichtung sind wir beispielsweise an der Frage interessiert, ob NP-vollständige Probleme von Schaltkreisen polynomieller Größe berechnet werden können. Interessanterweise lassen sich hier enge Querbezüge zur Frage der Erlernbarkeit von spezifischen Konzeptklassen herstellen.
- Weitere Forschungsinteressen der Gruppe liegen in den Bereichen Algorithmisches Lernen und Kryptografie. Diese Gebiete haben ihre Fundamente in der Komplexitätstheorie und machen stark von komplexitätstheoretischen Begriffsbildungen und Methoden Gebrauch. Wie im letzten Absatz bereits angesprochen, gilt unser Hauptinteresse hierbei der Erforschung von Querbezügen zwischen den genannten Gebieten, wobei Angluins Modell des "Exakten Lernens durch Fragen" und Valiants Modell des "PAC-learning" (PAC = probably approximately correct) im Vordergrund stehen. So konnten wir beispielsweise eine enge Verbindung zwischen der Existenz von kryptografisch sicheren Pseudozufallsgeneratoren und der verteilungsspezifischen PAC-Erlernbarkeit aufzeigen. In einem eher praktisch orientierten Forschungsprojekt sollen Sicherheitsmodelle für IT-Sicherheitssysteme untersucht werden, die eine zuverlässige Evaluierung nach bestimmten Sicherheitskriterien ermöglichen.
- Bekanntermaßen lassen sich komplexitätstheoretische Fragestellungen wie etwa NP =? coNP mit der Beweislänge von Tautologien in aussagenlogischen Beweissystemen in Verbindung bringen. Damit verknüpft ist die Frage nach der Existenz von optimalen Beweissystemen für die Menge der aussagenlogischen Tautologien oder für andere Sprachen. Hier ist es gelungen, auch diese Fragestellung mit rein komplexitätstheoretischen Fragen wie die Existenz von vollständigen Problemen für Promise-Klassen in Verbindung zu bringen.
- Schließlich gehen wir der Frage nach, ob sich das Paradigma der Parametrisierten Komplexität auf Gebiete wie Algorithmisches Lernen oder Kryptografie anwenden lässt.
Die aktuellen Forschungsprojekte des Lehrstuhls können Sie hier finden.
Im wöchentlichen Forschungsseminar werden Vorträge zu aktuellen Forschungsthemen gehalten.
Weiterhin beteiligt sich unser Lehrstuhl am Oberseminar Theoretische Informatik.