Michaelis Yannakakis ( Greek Μιχάλης Γιαννακάκης , born Mihalis Yannakakis ; born September 13, 1953 , Athens , Greece ) is a Greek computer scientist , professor at Columbia University ( New York , USA ). Known for his work in the field of complexity theory of computing , databases and other related fields. Winner of the Whip Award ( 2005 ). Member of the US National Academy of Sciences (2018) [1] .
| Michalis Yannakakis | |
|---|---|
| Greek Μιχάλης Γιαννακάκης | |
| Date of Birth | September 13, 1953 (66 years old) |
| Place of Birth | Athens , Greece |
| A country | |
| Scientific field | theory of computational complexity , Database |
| Place of work |  Columbia University |
| Alma mater | Athens National Technical University |
| supervisor | Jeffrey Ullman |
| Awards and prizes | Bell Labs Distinguished Member of Technical Staff Award ( 1985 ) Bell Labs President's Gold Award ( 2000 ) Knut Award ( 2005 ) |
Content
- 1 Education and career
- 2 Research
- 3 Awards
- 4 notes
- 5 Links
Education and Career
Michalis Yannakakis was born in Athens on September 13, 1953 and attended the Varvakio Experimental Gymnasium (Greek Βαρβάκειο Πειραματικό Γυμνάσιο) for early education in Psychiko (Athens).
In 1975 , he graduated from the Athens National Technical University with a diploma in electrical engineering, and in 1979 received a Ph.D. in computer science from Princeton University ( USA ). His dissertation was entitled The Complexity of Maximum Subgraph Problems . [2]
In 1978, Michalis Yannakakis joined the Bell Lab Corporation ( Murray Hill , New Jersey , USA ) and in 1991-2001. was director of the Information Technology Fundamentals Research Division. He then left Bell Laboratories and joined Avaya Labs. There, Yannakakis was director of the Information Technology Fundamentals Research Division until 2002 .
In 2002 , Yannakakis became professor of computer science at Stanford University , where he remained until 2003 .
From 2004 to the present, he has been a professor of computer science at Columbia University .
From 1992 to 2003 Yannakakis worked in the editorial board of SIAM Journal on Computing (SICOMP), from 1998 to 2003 . was its editor in chief. In 1986 - 2000 he also served on the editorial board of the Journal of the Computer Science Association . Michalis Yannakakis works in the editorial boards of several other journals, including the Journal of Computer and System Sciences , the Journal of Combinatorial Optimization, and the Journal of Complexity . He was also a member of the consensus committees and chaired various conferences such as ACM Symposium on Principles of Database Systems (PODS) and IEEE Symposium on Foundations of Computer Science.
As of November 2015 , the scientific publications of Michalis Yannakakis have been cited about 27,000 times, and its h-index is 86. [3]
Research Work
Michalis Yannakakis is known for his contributions to computer science in areas such as computational complexity theory, database theory , automated verification and testing, and algorithmic graph theory .
A special place among the scientist's valuable achievements in the field of complexity theory is occupied by two key works on the topics of the theory of probabilistically verifiable evidence and the complexity of approximation . In 1988 , at the annual Symposium on Computational Theory , funded by the Association of Computing Engineering (AVT) , Michalis Yannakakis and Christos Papadimitriou presented definitions of the complexity classes Max-NP and Max-SNP (a subclass of Max-NP) containing a number of interesting optimization problems. Yannakakis and Papadimitriou have shown that these tasks have some limited error. With the help of these conclusions, it became possible to explain the lack of progress in the study of the approximability of a number of optimization problems seen in the research community, including the “ 3-feasibility ” problem, the independent set problem , and the traveling salesman problem . [four]
In 1993 , at the next ABT symposium on computation theory, Michalis Yannakakis and Karsten Lund presented a number of important conclusions regarding the problems of approximation calculations. These results showed the difficulty of efficiently calculating approximate solutions to a number of minimization problems, such as the case of graph coloring and the problem of covering a set . Given the unlikely that such NP-hard problems will be solved optimally in polynomial time , many attempts have been made to develop effective approximate solutions for them. The results obtained by Yannakakis and Karsten showed a low probability of achieving this goal. [5]
In the field of database theory, the main contribution of Michalis Yannakakis is the initiation of research on acyclic databases and two-phase blocking. Acyclic database schemas are schemas that contain one acyclic connection dependency and a set of functional dependencies. [6] A number of researchers, including Yannakakis, noted the suitability of these schemes, demonstrating the many useful properties that they have: the ability to solve many problems based on acyclic schemes in polynomial time, despite the fact that the problem could be NP-complete for other schemes. [7]
Awards and Prizes
He was awarded the Knut Prize ( 2005 ) for the significance, influence and amazing degree of his contribution to the theoretical foundations of computer technology, and also won two awards from the Bell Labs: Distinguished Member of Technical Staff Award ( 1985 ) and President's Gold Award ( 2000 ). He is a member of the Association of Computer Engineering and the Bell Lab Research Center.
Notes
- ↑ National Academy of Sciences Members and Foreign Associates Elected . NAS (May 1, 2018).
- ↑ The Mathematics Genealogy Project - Mihalis Yannakakis (accessed December 9, 2009)
- ↑ Googel Scholar Record of M. Yannakakis .
- ↑ Christos Papadimitriou, Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 2–4, 1988.
- ↑ Carsten Lund, Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p. 286-293, May 16–18, 1993.
- ↑ 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, p. 355-362, 11-13 May 1981.
- ↑ Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p. 479-513, July 1983.