Derandomisierung von Polynom Identitätstests und dem Isolation Lemma

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