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

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