Record #259661 - GSI Repository

DFG project G:(GEPRIS)416961355

Test von Polynomgleichungen und algebraische Komplexität

Coordinator	Professor Dr. Thomas Thierauf
Grant period	2019 -
Funding body	Deutsche Forschungsgemeinschaft
	DFG
Identifier	G:(GEPRIS)416961355

Note: 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.

Recent Publications

There are no publications

Record created 2023-01-19, last modified 2024-09-28

Similar records

Add to personal basket
Export as Author List with IDs BibTeX (UTF-8), EndNote XML, EndNote Text, RIS, MARC, Print MARC, MARCXML, DC,
Request correction
Submit fulltext

GSI Homepage \| GSI Library \| English Deutsch \| guest :: login GSI Repository
Search	Submit	Personalize Your alerts Your baskets Your searches	Help