Derandomisierung von Polynom Identitätstests und dem Isolation Lemma

Antragsteller Professor Dr. Thomas Thierauf
Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2010 bis 2019
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 167224914
 

Projektbeschreibung

Eine Reihe wichtiger algorithmischer Probleme haben einen algebraischen Charakter. Fragen zur Effizienz von Lösungsverfahren für solche Probleme motivieren die Forschung im Bereich Komplexitätstheorie. Prominente Beispiele dafür sind Primzahltests, perfekte Matching oder Äquivalenzprobleme für verschiedene Schaltkreise oder branching programs.Die gemeinsame Eigenschaft dieser Probleme ist, dass sie in Gleichungen von Polynomen übersetzt werden können. Randomisierte Algorithmen prüfen solche Gleichungen indem sie die Polynome an zufälligen Punkten auswerten. Der Primzahltest von Agrawal, Kayal und Saxena kann als Teil eines allgemeineren Programms der Derandomisierung gesehen werden, eines der aktivsten Forschungsfelder innerhalb der Komplexitätstheorie. Ziel des Projekts ist es, für weitere Probleme eine Derandomisierung unter Ausnutzung der jeweiligen algebraischen Strukturen zu erhalten.
DFG-Verfahren Sachbeihilfen
Internationaler Bezug Indien
Beteiligte Person Professor Dr. Manindra Agrawal