Nichtuniforme Komplexität konkreter Probleme

• Applicant: Dr. Martin Sauerhoff
• Subject Area: Theoretical Computer Science
• Term: from 2004 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5425788

Branchingprogramme (BPs) gehören zu den nichtuniformen Berechnungsmodellen, deren Entwicklung in den letzten Jahren eine besonders stürmische Entwicklung erfahren haben. Mit Hilfe von BPs kann man inzwischen für spezielle Probleme bereits superlineare Zeitschranken bei sublinearem Platz für allgemeine RAMs nachweisen. Hier soll die Entwicklung der unteren Schranken für BPs weiter vorangetrieben werden. Neben der Teilnahme am Wettbewerb um die besten unteren Schranken für die Größe wollen wir uns um die Verbesserung der vorhandenen Techniken für nichtdeterministische, randomisierte, approximierende und quantenmechanische Varianten von BPs kümmern, für die es auch im Fall einiger eingeschränkter Modelle noch interessante offene Probleme gibt. Außerdem sollen Anwendungen von Techniken zum Nachweis unterer Schranken in den Themenbereichen Entscheidungslisten und Einwegfunktionen sowie am Rande auch noch offene Fragen zur Komplexität von Algorithmen untersucht werden. Darüber hinaus wollen wir die im Bereich BPs erarbeiteten grundlegenden Techniken, insbesondere aus der Kommunikationskomplexitätstheorie, auch bei neueren, durch die Praxis motivierten Modellen für spezielle Arten von Algorithmen zum Einsatz bringen. Dazu gehören Cell-Probe-Komplexität, Modelle für Algorithmen auf Datenströmen und Property-Testing.

• DFG Programme: Research Grants