Mihalis Yannakakis (Greek: Μιχάλης Γιαννακάκης; born 13 September 1953 in Athens, Greece)[1] is a professor of computer science at Columbia University.

[2][3] Yannakakis was born in Athens, Greece in 1953 and attended Varvakeio High School for his early education.

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.

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.

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