Mihalis Yannakakis

Mihalis Yannakakis
Mihalis Yannakakis 2006.jpg
Mihalis Yannakakis
Geboren 13. September 1953 (Alter 68)
Athen, Griechenland
Staatsangehörigkeit griechisch-amerikanisch
Alma Mater Nationale Technische Universität von Athen
Princeton Universität
Auszeichnungen Knuth -Preis (2005)
Wissenschaftliche Karriere
Felder Informatik
Institutionen Universität von Columbia
Doktorand Jeffrey Ullman

Mihalis Yannakakis (griechisch: Μιχάλης Γιαννακάκης; Geboren am 13. September 1953 in Athen, Griechenland)[1] ist Professor für Informatik bei Universität von Columbia. Er ist bekannt für seine Arbeit in Rechenkomplexität, Datenbankenund andere verwandte Felder. Er gewann die Donald E. Knuth Preis im Jahr 2005.[2][3]

Ausbildung und Karriere

Yannakakis wurde 1953 in Athen, Griechenland, geboren und besuchte Varvakeio High School für seine frühe Ausbildung. Er absolvierte die Nationale Technische Universität von Athen 1975 mit einem Diplom in Elektrotechnik und promovierte dann in Informatik Princeton Universität 1979.[1] Seine Dissertation hatte den Titel "Die Komplexität maximaler Subgraph -Probleme".[4]

1978 schloss er sich bei Glockenlabors und diente als Direktor der Forschungsabteilung für Computerprinzipien von 1991 bis 2001, als er Bell Laboratories verließ und sich Avaya Laboratories anschloss. Dort war er bis 2002 Direktor der Forschungsabteilung für Computerprinzipien.[1]

Im Jahr 2002 schloss er sich bei Universität in Stanford, wo er Professor für Informatik war und 2003 gegangen ist, um sich anzuschließen Universität von Columbia Im Jahr 2004, wo er derzeit als Percy K. und diente Vida L. W. Hudson Professor für Informatik.[1]

Von 1992 bis 2003 war Yannakakis Mitglied des Redaktionsvorstands der Siam Journal über Computing und war das Chefredakteur Zwischen 1998 und 2003. war er auch Mitglied des Redaktionsvorstands der Journal of the ACM von 1986 bis 2000.[1] Weitere Mitgliedschaften des Redaktionsvorstands sind die Journal of Computer and System Sciences, das Journal of Combinatorial Optimization, und die Journal of Complexity. Er war auch in Konferenzausschüssen tätig und leitete verschiedene Konferenzen, wie die ACM -Symposium über Prinzipien von Datenbanksystemen und die IEEE -Symposium über Fundamente der Informatik.[1]

Ab Juni 2020 wurden seine Veröffentlichungen fast 35.000 Mal zitiert, und er hat eine H-Index von 93.[5]

Forschung

Yannakakis ist bekannt für seine Beiträge zur Informatik in den Bereichen von Computerkomplexitätstheorie, Datenbanktheorie, computergestützte Überprüfung und Prüfung und Algorithmische Graphentheorie.

Zu seinen Beiträgen zur Komplexitätstheorie gehören zwei Artikel über die PCP -Theorie und über Annäherungshärte. Im Jahr ACM -Symposium über die Theorie des Computers von 1988 Yannakakis und Christos Papadimitriou stellte die Definitionen der Komplexitätsklassen Max-NP und Max-SNP ein. Max-NP und Max-SNP (eine Unterklasse von max-np) enthalten eine Reihe interessanter Optimierungsprobleme, und sie wurde von Yannakakis und Papadimitriou gezeigt, dass diese Probleme einen gewissen begrenzten Fehler haben. Diese Ergebnisse konnten den mangelnden Fortschritt erklären, der in der Forschungsgemeinschaft auf die Annäherung an eine Reihe von Optimierungsproblemen zu sehen war, einschließlich 3sat, das Unabhängiges Problem, und die Problem mit reisenden Verkäufern.[6]

Yannakakis und Carsten Lund präsentierte eine Reihe von Ergebnissen bezüglich der Härte der Berechnung von Näherungen auf dem jährlichen ACM -Symposium zur Berechnungstheorie von 1993. Diese Ergebnisse zeigten die Schwierigkeit, ungefähre Lösungen für eine Reihe von Minimierungsproblemen wie z. B. effizient zu berechnen Grafikfarbe und Set Deckung. Angesichts des unwahrscheinlichen Szenarios, das Np-harte Probleme wie Diagrammfärben und eingestelltes Abdeckungsabdeckung würden optimal gelöst in PolynomzeitEs gab viele Versuche, effiziente Annäherungslösungen für sie zu entwickeln. Die von Yannakakis und Carsten erzielten Ergebnisse erwiesen die Unwahrscheinlichkeit, diese Aufgabe zu erreichen.[7]

In der Gegend von DatenbanktheorieZu seinen Beiträgen gehört die Einleitung der Studie von acyclisch Datenbanken und nicht zwei Phasenverriegelung. Acyclische Datenbankschemata sind Schemata, die eine einzelne Acyclic enthalten Abhängigkeit beitreten (Eine Abhängigkeit von Join ist eine Beziehung, die das Verbinden von Tabellen der Datenbank verbindet) und eine Sammlung funktionaler Abhängigkeiten.[8] Eine Reihe von Forschern, darunter Yannakakis, wies auf die Nützlichkeit dieser Systeme hin, indem sie die vielen nützlichen Eigenschaften demonstrieren, die sie hatten: beispielsweise die Fähigkeit, viele acyclisch-scheme-basierte Probleme in der Polynomzeit zu lösen, während das Problem leicht NP- gewesen sein konnte. Vollständig für andere Programme.[9]

In Bezug auf non Zwei-Phasen-VerriegelungYannakakis zeigte, wie Kenntnisse über die Struktur einer Datenbank und die Formen verschiedener Transaktionen verwendet werden könnten, um festzustellen, ob eine bestimmte Verriegelungsrichtlinie sicher ist oder nicht. Die häufig verwendeten Richtlinien für zwei Phasenverriegelung (2PL) bestehen aus zwei Stufen - zum Verriegeln bzw. die Entsperren - und um eine solche Richtlinie zu vermeiden, muss die Entitäten einer Datenbank eine gewisse Struktur auferlegen. Die Ergebnisse von Yannakakis zeigen, wie, indem sie a Hypergraph Unter der Konsistenzbeschränkungstruktur einer Datenbank ist eine Verriegelungsrichtlinie, die Entitäten entlang der Pfade dieses Hypergraphen besucht. Eine solche Richtlinie muss nicht zweiphasige sein und diese Richtlinien können nach der Konnektivität des oben genannten Hypergraphen klassifiziert werden, wobei 2PL-Richtlinien nur eine bestimmte Instanz davon sind.[10] Yannakakis zeigte weiter, dass für die natürliche Klasse der sicheren Verriegelungsrichtlinien (L-Policies) Freiheit von Deadlocks ausschließlich von der Reihenfolge bestimmt wird, in der auf Einheiten durch Transaktionen zugegriffen werden, und aus diesen abgeleiteten einfachen Bedingungen, die die Freiheit von Deadlocks für die Freiheit garantieren würden Eine L-Policy.[11]

Er hat auch zum Bereich der computergestützten Überprüfung und Tests beigetragen, wo er die strengen algorithmischen und komplexitätstheoretischen Grundlagen des Feldes legte. Einige seiner Beiträge umfassen die Gestaltung von Speicher-effizienten Algorithmen zur Überprüfung der zeitlichen Eigenschaften von Finite-State-Programmen,[12] Bestimmung der Komplexität des Testens, ob Programme ihre Spezifikationen erfüllen, die in ausgedrückt werden lineare Zeit zeitliche Logik,[13] und zu überprüfen, ob ein Modell mit Zeitbeschränkungen ein bestimmtes zeitliches Eigentum erfüllt.[14] Zusammen mit Alex Groce und Doron Peled stellte er adaptive Modellprüfung ein und zeigte, dass die Ergebnisse der Überprüfung verwendet werden können, um das Modell zu verbessern, wenn Inkonsistenzen zwischen einem System und dem entsprechenden Modell vorhanden sind.[15] Er hat auch zur Erforschung von beigetragen Nachrichtensequenzdiagramme(MSC), wo es so schwach gezeigt wurde Realisierbarkeit ist für begrenzte MSC-Graphen unentscheidbar und diese sichere Realisierbarkeit ist in Expacezusammen mit anderen interessanten Ergebnissen im Zusammenhang mit der Überprüfung von MSC-Graphen.[16]

Auszeichnungen und Anerkennung

Yannakakis ist Mitglied beides Nationale Akademie des Ingenieurwesens und die Nationale Akademie der Wissenschaften. Er wurde mit dem siebten Zeitpunkt ausgezeichnet Knuth -Preis für seine Beiträge zur theoretischen Informatik.[3] Er wurde auch 1985 und 2000 mit dem Distinguished -Mitglied des technischen Staff Award und dem Gold Award des Bell Labs Presidents Gold ausgezeichnet. Er ist Stipendiat der ACM und auch ein Fellow von Glockenlabors.[1] Er wurde zum Stipendiaten der American Academy of Arts and Sciences (AAAS) im Jahr 2020.[17]

Verweise

  1. ^ a b c d e f g Columbia University: Lebenslauf: Mihalis Yannakakis (Zugriff am 12. November 2009)
  2. ^ 2005 KNUTH PREIS MIHALIS YANNAKAKIS, ACM, 1. Mai 2006
  3. ^ a b Knuth -Preis
  4. ^ Das Mathematik -Genealogie -Projekt - Mihalis Yannakakis (Zugriff am 9. Dezember 2009)
  5. ^ "Googel Scholar -Aufzeichnung von M. Yannakakis".
  6. ^ Christos Papadimitriou, Mihalis Yannakakis, Optimierung, Näherung und Komplexitätsklassen, Verfahren des zwanzigsten jährlichen ACM -Symposiums über die Theorie des Computing, S. 229–234, 2. bis 4. Mai 1988.
  7. ^ Carsten Lund, Mihalis Yannakakis, über die Härte der Approximierungsprobleme, Verfahren des fünfundzwanzigsten jährlichen ACM-Symposiums über die Theorie des Computers, S. 286–293, 16. bis 18. Mai 1993.
  8. ^ Catriel Beeri, Ronald Fagin, David Maier, Alberto Mendelzon, Jeffrey Ullman, Mihalis Yannakakis, Eigenschaften von acyclischen Datenbankschemata, Verfahren des dreizehnten jährlichen ACM -Symposiums über die Theorie der Berechnung, S. 355–362, 11–13 Mai 1981.
  9. ^ Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis, Über die Wünschbarkeit von acyclischen Datenbankschemata, Journal of the ACM, V.30 N.3, S. 479–513, Juli 1983.
  10. ^ Mihalis Yannakakis, Eine Theorie der sicheren Verriegelungsrichtlinien in Datenbanksystemen, Journal of the ACM, V.29 N.3, S. 718–740, Juli 1982.
  11. ^ Mihalis Yannakakis, Freiheit von Deadlocks of Safe Locking-Richtlinien, Siam J. über Computing 11 (1982), 391-408.
  12. ^ C. Courcoubetis, M. Vardi, P. Wolper, M. Yannakakis, Gedächtniseffiziente Algorithmen zur Überprüfung zeitlicher Eigenschaften, formale Methoden im Systemdesign, v.1 n.2-3, S. 275–288, Okt. 1992.
  13. ^ Costas Courcoubetis, Mihalis Yannakakis, Die Komplexität der probabilistischen Überprüfung, Journal of the ACM, V.42 N.4, S. 857–907, Juli 1995.
  14. ^ R.
  15. ^ Groce, A., Peled, D. und Yannakakis, M. 2002. Adaptive Modellprüfung. In Proceedings der 8. Internationalen Konferenz über Tools und Algorithmen für den Bau und die Analyse von Systemen (8. bis 12. April 2002). J. Katoen und P. Stevens, Hrsg. Vorlesungsnotizen in Informatik, Vol. 2280. Springer-Verlag, London, 357-370.
  16. ^ Rajeev Alur, Kousha Etessami, Mihalis Yannakakis, Realisierbarkeit und Überprüfung von MSC -Diagrammen, Theoretische Informatik, V.331 N.1, S. 97–114, 15. Februar 2005.
  17. ^ "AAAS -Stipendiaten gewählt" (PDF). Mitteilungen der American Mathematical Society.

Externe Links