Mihalis Yannakakis

Das Diplom in Elektrotechnik, das Mihalis Yannakakis 1975 von der Technischen Nationalen Universität Athen erhielt, markierte den Beginn einer langen Karriere in der theoretischen Informatik. Er wurde 1953 in Athen geboren und erwarb später einen Doktortitel in Informatik an der Princeton University, was sich nachhaltig auf die Datenbanktheorie, Verifikation und algorithmische Graphentheorie auswirkte.

Grundlagen der Komplexität

Yannakakis verbrachte über zwei Jahrzehnte in der Industrieforschung und begann seine Tätigkeit 1978 in den Bell Laboratories. Von 1991 bis 2001 leitete er dort als Direktor die Forschungsabteilung für Rechenprinzipien. In dieser Zeit arbeitete er 1988 mit Christos Papadimitriou zusammen, um die Komplexitätsklassen Max-NP und Max-SNP zu definieren. Dies lieferte eine rigorose Erklärung für die Einschränkungen bei der Annäherung an NP-schwere Probleme wie das Handlungsreisendenproblem und 3SAT. Seine Arbeit mit Carsten Lund aus dem Jahr 1993 verdeutlichte zudem die inhärente Schwierigkeit, Näherungslösungen für Minimierungsprobleme wie die Graphfärbung zu berechnen.

Datenbank-Innovationen

Seine Beiträge zur Datenbanktheorie konzentrierten sich auf die Optimierung der Anfrageverarbeitung durch die Untersuchung azyklischer Schemata. Er führte den Yannakakis-Algorithmus für azyklische konjunktive Anfragen ein und zeigte, dass diese Strukturen in polynomialer Zeit gelöst werden können. Neben der Anfrageoptimierung untersuchte er Sperrrichtlinien und bewies, dass die Sicherheit von Datenbanken außerhalb der starren Beschränkungen des Zwei-Phasen-Sperrens aufrechterhalten werden kann, indem die Hypergraphenstruktur der Daten und Transaktionskonsistenzbeschränkungen zur Vermeidung von Verklemmungen genutzt werden.

Verifikation und akademische Führung

Yannakakis wechselte in die akademische Welt und hatte 2002 eine Professur an der Stanford University inne, bevor er 2004 an die Columbia University wechselte. Derzeit ist er Percy K. and Vida L. W. Hudson Professor für Informatik. Seine Forschung im Bereich der computergestützten Verifikation schuf algorithmische Grundlagen zum Testen linearer temporaler Logik und von Nachrichtensequenzdiagrammen. Zudem entwickelte er gemeinsam mit Alex Groce und Doron Peled das adaptive Modellprüfen, eine Methode zur Verfeinerung von Systemmodellen basierend auf Verifikationsergebnissen.

Professionelle Anerkennung

Yannakakis war redaktionell stark engagiert und fungierte von 1998 bis 2003 als Chefredakteur des SIAM Journal on Computing. Sein akademisches Ansehen spiegelt sich in seiner Mitgliedschaft in der National Academy of Sciences, der National Academy of Engineering, der American Academy of Arts and Sciences und der Academia Europaea wider. Zu seinen Auszeichnungen gehören der Knuth-Preis 2005 und der John von Neumann Theory Prize 2023.

Steckbrief

- Geboren: 1953, Athen, Griechenland - Promotion: Princeton University, 1979 - Knuth-Preis: 2005 - John von Neumann Theory Prize: 2023 - ACM Fellow: 1998 - Staatsbürgerschaft: Vereinigte Staaten; Griechenland - Sprachen: Neugriechisch

Häufig gestellte Fragen

### Was ist der Yannakakis-Algorithmus?

Es handelt sich um eine Methode zur Ausführung azyklischer konjunktiver Anfragen in Datenbanksystemen, wodurch diese in polynomialer Zeit gelöst werden können.

### Mit welchen Institutionen war Yannakakis verbunden?

Er hat bei den Bell Laboratories, Avaya Laboratories, der Stanford University und der Columbia University gearbeitet.