Giannakakis, Michalis

Michalis Yannakakis ( græsk Μιχάλης Γιαννακάκης , engelsk  Mihalis Yannakakis ; født 13. september 1953 , Athen , Grækenland ) er en græsk datamatiker , professor ved Columbia University ( New York University ) , professor ved Columbia University . Kendt for sit arbejde inden for beregningsmæssig kompleksitetsteori , databaser og andre relaterede felter. Vinder af Knuth-prisen ( 2005 ). Medlem af US National Academy of Sciences (2018) [1] .

Uddannelse og karriere

Michalis Giannakakis blev født i Athen den 13. september 1953 og for sin tidlige uddannelse gik han på Varvakio Experimental Gymnasium (græsk: Βαρβάκειο Πειραματικό Γυϼά) i Psycho-μάάάμαματικό Γυϼάάνονάμά.

I 1975 dimitterede han fra National Technical University of Athens med en grad i elektroingeniør, og i 1979 modtog han en Ph.D. -grad i datalogi fra Princeton University ( USA ). Hans afhandling fik titlen " The Complexity of Maximum Subgraph Problemer ". [2]

I 1978 sluttede Michalis Giannakakis sig til Bell Lab Corporation ( Murray Hill , New Jersey , USA ) og i 1991-2001. Han var direktør for Information Technology Fundamentals Research Division. Han forlod derefter Bell Laboratories og sluttede sig til Avaya Labs. Der var Giannakakis direktør for Information Technology Fundamentals Research Division indtil 2002 .

I 2002 overtog Giannakakis som professor i datalogi ved Stanford University , hvor han blev indtil 2003 .

Fra 2004 til i dag har han været professor i datalogi ved Columbia University .

Fra 1992 til 2003  _ Giannakakis tjente i redaktionen for SIAM Journal on Computing (SICOMP )  fra 1998-2003 . var dens chefredaktør. I 1986 - 2000  _ han tjente også i redaktionen af ​​Journal of the Association for Computing Machinery . Michalis Giannakakis tjener i redaktionen af ​​en række andre tidsskrifter, herunder Journal of Computer and System Sciences , Journal of Combinatorial Optimization og Journal of Complexity . Han har også tjent i forligsudvalg og været formand for forskellige konferencer såsom ACM Symposium on Principles of Database Systems (PODS) og IEEE Symposium on Foundations of Computer Science.    

I november 2015 er Michalis Giannakakis' videnskabelige publikationer blevet citeret omkring 27.000 gange, og hans h-indeks er 86. [3]

Forskningsarbejde

Michalis Giannakakis er kendt for sine bidrag til datalogi inden for områder som beregningskompleksitetsteori , databaseteori , automatiseret verifikation og testning og algoritmisk grafteori .

En særlig plads blandt videnskabsmandens værdifulde resultater inden for kompleksitetsteori er optaget af to nøgleværker om emnerne i teorien om sandsynligt verificerbare beviser og kompleksitet af tilnærmelse . I 1988 præsenterede Michalis Giannakakis og Christos Papadimitriou definitionerne af Max-NP og Max-SNP kompleksitetsklasser (som er en underklasse af Max-NP) på det årlige Association for Computing Machinery (AUT) finansierede Symposium on Theory of Computation , indeholdende en række interessante optimeringsproblemer. Giannakakis og Papadimitriou viste, at disse problemer har nogle begrænsede fejl. Ved hjælp af disse resultater blev det muligt at forklare manglen på fremskridt, der blev bemærket i forskningsmiljøet i undersøgelsen af ​​tilnærmeligheden af ​​en række optimeringsproblemer, herunder " 3-tilfredshedsproblemet " , det uafhængige sæt -problem og rejsende sælger problem . [fire]

I 1993 præsenterede Michalis Giannakakis og Karsten Lund på det regelmæssige AVT -symposium om beregningsteori en række vigtige konklusioner vedrørende spørgsmålet om beregningsmæssige tilnærmelser . Disse resultater viste vanskeligheden ved effektivt at beregne omtrentlige løsninger på en række minimeringsproblemer, såsom tilfældet med graffarvning og sætdækningsproblemet . I betragtning af usandsynligheden for, at sådanne NP-hårde problemer vil blive løst optimalt i polynomiel tid , er der gjort mange forsøg på at udvikle effektive omtrentlige løsninger til dem. Resultaterne opnået af Giannakakis og Carsten beviste, at dette mål næppe ville blive nået. [5]

Inden for databaseteori er hovedbidraget fra Michalis Giannakakis initieringen af ​​forskning i acykliske databaser og ikke-to-fase blokering. Acykliske databaseskemaer er skemaer, der indeholder én acyklisk forbindelsesafhængighed og et sæt funktionelle afhængigheder. [6] En række forskere, herunder Giannakakis, har bemærket anvendeligheden af ​​disse skemaer og demonstrerer de mange nyttige egenskaber, de har: evnen til at løse mange problemer baseret på acykliske skemaer i polynomisk tid, på trods af at problemet kunne være NP -komplet for andre ordninger. [7]

Priser og præmier

Han blev tildelt Knuth-prisen ( 2005 ) for betydningen, indflydelsen og forbløffende omfang af hans bidrag til computerens teoretiske grundlag og modtog også to priser fra Bell Labs: Distinguished Member of Technical Staff Award ( 1985 ) og President's Gold Award ( 2000 ). Han er medlem af Association for Computing Machinery og et forskningscenter hos Bell Labs .

Noter

1. ↑ National Academy of Sciences medlemmer og udenlandske associerede valgt . NAS (1. maj 2018). (ubestemt)
2. ↑ The Mathematics Genealogy Project - Mihalis Yannakakis (tilganget 9. december 2009)
3. ↑ Google Scholar Record af M. Yannakakis . (ubestemt)
4. ↑ Christos Papadimitriou, Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, s.229-234, 2-4 maj 1988.
5. ↑ Carsten Lund, Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the 25th annual ACM symposium on Theory of computing, s.286-293, 16-18 maj 1993.
6. ↑ Catriel Beeri, Ronald Fagin, David Maier, Alberto Mendelzon, Jeffrey Ullman, Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, s.355-362, 11-13 maj 19819.
7. ↑ Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, s.479-513, juli 1983.

Links

• Data Science Institute
• Mihalis Yannakakis