Test von Polynomgleichungen und algebraische Komplexität

• Antragsteller: Professor Dr. Thomas Thierauf
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 416961355

Das Problem Polynom Identitätstest (PIT) -- entscheide, ob ein Polynom gegeben als arithmetischer Schaltkreis das Nullpolynom ist -- spielt eine zentrale Rolle in der arithmetischen Schaltkreis Komplexitätstheorie. PIT wird in vielen fundamentalen Resultaten der Komplexitätstheorie benützt, wie zum Beispiel Primzahltest, das PCP-Theorem und vielen anderen Problemen, die als Polynomgleichungen formuliert werden können. Es gibt effiziente randomisierte Algorithmen für PIT und eine der größten Herausforderungen in der Komplexitätstheorie ist es effiziente deterministische Algorithmen für das Problem zu finden. Eine allgemeine Derandomisierung von randomisierten Komplexitätsklassen wird als ein sehr schwieriges Problem angesehen, da man weiß, dass daraus starke untere Schranken für Schaltkreise folgen. Auf der anderen Seite gibt es Resultate wie den berühmten AKS-Primzahltest der zeigt, dass Derandomisierung für spezifische Probleme mit gewissen algebraischen Strukturen möglich ist. Ein prominenter Kandidat ist das perfekte Matching Problem (für parallele Algorithmen) und Verallgemeinerungen zu Matroiden. Das Ziel des Projekts ist es Derandomisierungen von weiteren, allgemeineren Strukturen zu bekommen. Durch die Verbindung zu PIT sind untere Schranken für arithmetische Berechnungsmodelle im Fokus, wie zum Beispiel arithmetische Schaltkreise, branching Prgramme oder Formeln. Dies motiviert auch Abgeschlossenheitseigenschaften der jeweiligen Komplexitätsklassen zu betrachten.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Indien
• Kooperationspartner: Professor Rohit Gurjar; Professor Dr. Nitin Saxena