Mihalis Yannakakis
Mihalis Yannakakis | |
---|---|
Born | |
Nationality | Greek-American |
Alma mater | National Technical University of Athens Princeton University |
Awards | Knuth Prize (2005) |
Scientific career | |
Fields | Computer science |
Institutions | Columbia University |
Doctoral advisor | Jeffrey Ullman |
Mihalis Yannakakis (
Education and career
Yannakakis was born in Athens, Greece in 1953 and attended Varvakeio High School for his early education. He graduated from the National Technical University of Athens in 1975 with a diploma in Electrical Engineering, and then earned his PhD in Computer Science from Princeton University in 1979.[1] His dissertation was entitled "The Complexity of Maximum Subgraph Problems".[4]
In 1978 he joined
In 2002 he joined Stanford University, where he was a professor of computer science, and left in 2003 to join Columbia University in 2004, where he is currently serving as the Percy K. and Vida L. W. Hudson Professor of Computer Science.[1]
From 1992 to 2003, Yannakakis served on the editorial board of the
As of June 2020, his publications have been cited close to 35,000 times, and he has an h-index of 93.[5]
Research
Yannakakis is known for his contributions to computer science in the areas of
Among his contributions to complexity theory are two papers about the
Yannakakis and
In the area of database theory, his contributions include the initiation of the study of acyclic database schemes, acyclic conjunctive queries, and non-two-phase locking. Acyclic database schemes are schemes that contain a single acyclic join dependency (a join dependency is a relationship governing the joining of tables of the database) and a collection of functional dependencies;[8] a number of researchers, including Yannakakis, pointed out the usefulness of these schemes by demonstrating the many useful properties they had: for example, the ability to solve many acyclic-scheme based problems in polynomial time, whereas the problem could easily have been NP-complete for other schemes.[9]
With regard to non two-phase locking, Yannakakis demonstrated how knowledge about the structure of a database and the forms of various transactions executed on them could be used to establish whether a particular locking policy is safe or not. The commonly used two phase locking (2PL) policies consist of two stages – for locking and unlocking entities respectively – and to avoid such a policy it is necessary to impose some structure on the entities of a database; Yannakakis' results show how, by choosing a hypergraph resembling the consistency constraint-structure of a database, a locking policy that visits entities along the paths of this hypergraph will be safe. Such a policy need not be two-phase and these policies can be classified according to the connectivity of the above-mentioned hypergraph, 2PL policies being only one particular instance of these.[10] Yannakakis went on to show that for the natural class of safe locking policies (L-policies), freedom from deadlocks is determined solely on the order in which entities are accessed by transactions, and from this derived simple conditions that would guarantee freedom from deadlocks for an L-policy.[11]
He has also contributed to the area of computer aided verification and testing, where he laid the rigorous algorithmic and complexity-theoretic foundations of the field. Some of his contributions include the designing of memory efficient algorithms for the verification of temporal properties of finite-state programs,
Awards and recognition
Yannakakis is a member of both the
References
- ^ a b c d e f g Columbia University: CV: Mihalis Yannakakis (accessed 12 November 2009)
- ^ 2005 Knuth Prize Mihalis Yannakakis, ACM, 1 May 2006
- ^ a b Knuth Prize
- ^ The Mathematics Genealogy Project – Mihalis Yannakakis (accessed 9 December 2009)
- ^ "Google 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, pp. 229–234, 2–4 May 1988.
- ^ Carsten Lund, Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 286–293, 16–18 May 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, pp. 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, v.30 n.3, pp. 479–513, July 1983.
- ^ Mihalis Yannakakis, A Theory of Safe Locking Policies in Database Systems, Journal of the ACM, v.29 n.3, pp. 718–740, July 1982.
- ^ Mihalis Yannakakis, Freedom from deadlocks of safe locking policies, SIAM J. on Computing 11 (1982), 391-408.
- ^ C. Courcoubetis, M. Vardi, P. Wolper, M. Yannakakis, Memory-efficient algorithms for the verification of temporal properties, Formal Methods in System Design, v.1 n.2-3, pp. 275–288, Oct. 1992.
- ^ Costas Courcoubetis, Mihalis Yannakakis, The complexity of probabilistic verification, Journal of the ACM, v.42 n.4, pp. 857–907, July 1995.
- ^ R. Alur, A. Itai, R. P. Kurshan, M. Yannakakis, Timing verification by successive approximation, Information and Computation, v.118 n.1, pp. 142–157, April 1995.
- ^ Groce, A., Peled, D., and Yannakakis, M. 2002. Adaptive Model Checking. In Proceedings of the 8th international Conference on Tools and Algorithms For the Construction and Analysis of Systems (8–12 April 2002). J. Katoen and P. Stevens, Eds. Lecture Notes in Computer Science, vol. 2280. Springer-Verlag, London, 357-370.
- ^ Rajeev Alur, Kousha Etessami, Mihalis Yannakakis, Realizability and verification of MSC graphs, Theoretical Computer Science, v.331 n.1, pp. 97–114, 15 February 2005.
- ^ "AAAS Fellows Elected" (PDF). Notices of the American Mathematical Society.