Mihalis Yannakakis

Mihalis Yannakakis (Greek: Μιχάλης Γιαννακάκης; born 13 September 1953 in Athens, Greece) is Professor of Computer Science at Columbia University. He is noted for his work in computational complexity, databases, and other related fields. He won the Donald E. Knuth Prize in 2005.

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 Ph.D. in Computer Science from Princeton University in 1979. His dissertation was entitled "The Complexity of Maximum Subgraph Problems".

In 1978 he joined Bell Laboratories and served as Director of the Computing Principles Research Department starting from 1991 until 2001, when he left Bell laboratories and joined Avaya Laboratories. There he served as Director of the Computing Principles Research Department until 2002.

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.

From 1992 to 2003, Yannakakis served on the Editorial board of the SIAM Journal on Computing and was the Editor-in-chief between 1998 and 2003. He also was a member of the editorial board of the Journal of the ACM from 1986 to 2000. Other editorial board memberships include the Journal of Computer and System Sciences, the Journal of Combinatorial Optimization, and the Journal of Complexity. He has also served on conference committees and chaired various conferences, such as the ACM Symposium on Principles of Database Systems and the IEEE Symposium on Foundations of Computer Science.

As of November 2015, his publications have been cited close to 27,000 times, and he has an h-index of 86.

Yannakakis is known for his contributions to computer science in the areas of computational complexity theory, database theory, computer aided verification and testing, and algorithmic graph theory.

Among his contributions to complexity theory are two papers about the PCP theory and about hardness of approximation. In the Annual ACM Symposium on Theory of Computing of 1988, Yannakakis and Christos Papadimitriou introduced the definitions of the complexity classes Max-NP and Max-SNP. Max-NP and Max-SNP (which is a subclass of Max-NP) contain a number of interesting optimization problems, and it was shown by Yannakakis and Papadimitriou that these problems have some bounded error. These findings were able to explain the lack of progress that had been seen in the research community on the approximability of a number of optimization problems, including 3SAT, the Independent Set problem, and the Travelling Salesman Problem.

Yannakakis and Carsten Lund presented a number of findings regarding the hardness of computing approximations at the Annual ACM Symposium on Theory of Computing of 1993. These findings demonstrated the difficulty of efficiently computing approximate solutions to a number of minimization problems such as Graph coloring and Set covering. Given the unlikely scenario that NP-hard problems such as Graph coloring and Set covering would be solved optimally in polynomial time, there had been many attempts to develop efficient approximation solutions for them; the results obtained by Yannakakis and Carsten proved the unlikelihood of achieving this task.

In the area of database theory, his contributions include the initiation of the study of acyclic databases and of 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; 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.

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. 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.

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, determining the complexity of testing whether programs satisfy their specifications expressed in linear-time temporal logic, and verifying that a model with timing constraints satisfies a given temporal property. Along with Alex Groce and Doron Peled, he introduced Adaptive Model Checking, showing that when inconsistencies are present between a system and the corresponding model, the results of the verification can be used to improve the model. He has also contributed to research on Message Sequence Charts(MSC), where it was shown that weak realizability is undecidable for bounded MSC-graphs and that safe-realizability is in EXPSPACE, along with other interesting results related to the verification of MSC-graphs.

Yannakakis is a member of both the National Academy of Engineering and the National Academy of Sciences. He was awarded the seventh Knuth prize for his contributions to theoretical computer science. He has also been awarded the Bell Labs Distinguished Member of Technical Staff Award and the Bell Labs President’s Gold Award, in 1985 and in 2000 respectively. He is a Fellow of the ACM and also a Fellow of Bell Laboratories.