Mihalis Yannakakis

from Wikipedia, the free encyclopedia

Mihalis Yannakakis ( Greek Μιχάλης Γιαννακάκης Michalis Giannakakis ; born September 13, 1953 in Athens ) is a Greek computer scientist.

Yannakakis at Columbia University in 2006

Yannakakis graduated from the National Technical University of Athens with a degree in electrical engineering in 1975 . In 1979 he received his PhD from Princeton University under Jeffrey Ullman . From 1978 he was at Bell Laboratories , where he headed the Computing Principles Research Department from 1991. From 2001 he held the same position at Avaya Laboratories in Basking Ridge ( New Jersey ). In 2002 he became a professor of computer science at Stanford University and from 2004 at Columbia University .

He deals with algorithm design and analysis, combinatorial optimization, databases (he specifically founded the study of acyclic databases), computer-aided test procedures and verification procedures, algorithmic graph theory and complexity theory. In 1988 he and Christos Papadimitriou introduced new complexity classes (Max-NP and its sub-class Max-SNP), which also include well-known problems such as the traveling salesman problem and 3-SAT . His work with Carsten Lund on the difficulty of obtaining approximation methods for NP-difficult minimization problems such as the graph coloring problem and the set coverage problem was also influential . In 1991 he published a work that combined the extension complexity of polytopes in combinatorial optimization with other complexity concepts.

In 1997 he became a Fellow of Bell Laboratories, in 1985 he received the laboratory's Distinguished Member of Technical Staff Award, and in 2000 he received the gold medal from the President of Bell Labs. In 2005 he received the Knuth Prize , for 2020 he was awarded the EATCS Award . He has been a Fellow of the Association for Computing Machinery (ACM) since 1998 . In 2013 he was admitted to the Academia Europaea as an external member , and in 2018 to the National Academy of Sciences . From 1992 to 2003 he was co-editor and from 1998 main editor of the SIAM Journal of Computing. He was also co-editor of the Journal of the ACM from 1986 to 2000 and has been co-editor of the Journal of Combinatorial Optimization since 1997 and of the Journal of Complexity since 2004.

In 2020 Yannakakis was elected to the American Academy of Arts and Sciences .

Web links

Individual evidence

  1. ↑ Papadimitriou, Yannakakis: Optimization, approximation, and complexity classes , Proceedings of the 20th annual ACM symposium on Theory of computing, May 1988, pp. 229-234
  2. ↑ Lund, Yannakakis: On the hardness of approximating minimization problems, Proceedings of the 25th annual ACM symposium on Theory of Computing, May 1993, pp. 286-293
  3. ^ Yannakakis, Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., Vol. 43, 1991, pp. 441-466
  4. ^ Membership directory: Mihalis Yannakakis. Academia Europaea, accessed January 22, 2018 .
personal data
SURNAME Yannakakis, Mihalis
ALTERNATIVE NAMES Giannakakis, Michalis; Γιαννακάκης, Μιχάλης (Greek)
BRIEF DESCRIPTION Greek computer scientist
DATE OF BIRTH September 13, 1953
PLACE OF BIRTH Athens