Paper von Professor der Hochschule Aalen in der Rubrik Research Highlights in den Communications of the ACM erschienen
Das Paper „ A Deterministic Parallel Algorithm for Bipartite Perfect Matching“ von Steve Fenner, Rohit Gurjar, Thomas Thierauf ist in den Communications of the ACM in der Rubrik Research Highlights erschienen. Die Rubrik CACM Research Highlights widmet sich den wichtigsten aktuellen Forschungsergebnissen, die in der Informatik veröffentlicht wurden. Die Beiträge in diesem Abschnitt werden zunächst von einem Redaktionskomitee oder einem Auswahlkomitee der ACM SIG nominiert und dann durch Abstimmung mit der CACM-RH-Redaktion ausgewählt. Eine Veröffentlichung in dieser Rubrik bietet eine unübertroffene Sichtbarkeit und gilt als bedeutende Auszeichnung.
Eine grundlegende Aufgabe in der theoretischen Informatik ist es zu verstehen, ob man mit Hilfe von Zufallbits mehr Probleme algorithmisch effizient lösen kann als ohne. Eines der extensiv untersuchten Probleme bei diesem Thema ist das des perfekten Matching. Das perfekte Matching-Problem hat einen randomisierten parallelen (NC) Algorithmus, der auf dem Isolation Lemma von Mulmuley, Vazirani und Vazirani basiert. Eine offene Frage ist, ob dieser Algorithmus derandomisiert werden kann. In diesem Artikel zeigen Prof. Thierauf und seine Kollegen eine fast vollständige Derandomisierung des Isolation Lemmas für das perfekte Matching-Problem in bipartiten Graphen. Sie lösen damit ein seit über 30 Jahren offenes Problem.
Den gesamten Artikel können Sie hier lesen.
Herzlichen Glückwunsch an Prof. Dr. Thomas Thierauf und seine Kollegen Steve Fenner und Rohit Gurjar.