Complexity analysis of voting systems, exact and critical problems, and symmetric alternation

• Applicant: Professor Dr. Jörg-Matthias Rothe
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2007
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5406018

In diesem Projekt werden komplexitätstheoretische Untersuchungen zu Wahlsystemen, exakten Optimierungsproblemen, kritischen Problemen und zur symmetrischen Alternation durchgeführt. Wahlsysteme sind Regeln, mit denen aus einer Gruppe von Kandidaten die Sieger einer Abstimmung bestimmt werden können. Neben der Frage der Fairness einer Wahl, die in der Politikwissenschaft untersucht wird, treten in der Informatik zunehmend algorithmische Fragen nach der effizienten Durchführbarkeit von Wahlen und ihrer Manipulierbarkeit in den Vordergrund. Beispielsweise sind vom Kemeny-Wahlsystem inspirierte Aggregationssysteme nützlich, um die Manipulation des Website-Rankings von Suchmaschinen und "Spamming" zu verhindern. In diesem Projekt werden insbesondere das Gewinner-, Ranking- und Manipulationsproblem verschiedener Wahlsysteme untersucht und komplexitätstheoretisch klassifiziert. Weiterhin werden Vollständigkeitsresultate von exakten Optimierungsproblemen und kritischen Problemen in den Stufen der booleschen Hierarchie über NP angestrebt. Schließlich soll der vor kurzem eingeführte Begriff der symmetrischen Alternation im Hinblick auf die Polynomialzeit-Hierarchie und die interaktiven Beweissysteme untersucht werden. Das aktuelle Forschungsgebiet der interaktiven Beweissysteme ist sowohl in der Komplexitätstheorie als auch in der Kryptographie von großer Bedeutung.

• DFG Programme: Research Grants