The diploma in Electrical Engineering that Mihalis Yannakakis received from the National Technical University of Athens in 1975 marked the beginning of a long career in computational complexity theory. Born in 1953 in Athens, he later earned a PhD in Computer Science at Princeton University, subsequently influencing database theory, verification, and algorithmic graph theory.
Foundations in Complexity
Yannakakis spent over two decades in industrial research, beginning his tenure at Bell Laboratories in 1978. He served as the Director of the Computing Principles Research Department there from 1991 to 2001. During this period, he collaborated with Christos Papadimitriou in 1988 to define the complexity classes Max-NP and Max-SNP, providing a rigorous explanation for the limitations observed in approximating NP-hard problems like the Travelling Salesman Problem and 3SAT. His 1993 work with Carsten Lund further clarified the inherent difficulty of computing approximate solutions for minimization problems such as Graph coloring.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Database Innovations
His contributions to database theory focused on the optimization of query processing through the study of acyclic schemes. He introduced the Yannakakis algorithm for acyclic conjunctive queries, demonstrating that these structures could be solved in polynomial time. Beyond query optimization, he investigated locking policies, proving that database safety could be maintained outside the rigid constraints of two-phase locking by utilizing the hypergraph structure of the data and transaction consistency constraints to prevent deadlocks.
Verification and Academic Leadership
Transitioning into academia, Yannakakis held a professorship at Stanford University in 2002 before joining Columbia University in 2004. He currently serves as the Percy K. and Vida L. W. Hudson Professor of Computer Science. His research in computer aided verification established algorithmic foundations for testing linear-time temporal logic and Message Sequence Charts. He also developed Adaptive Model Checking alongside Alex Groce and Doron Peled, a method that refines system models based on verification results.
Professional Recognition
Yannakakis has maintained a significant editorial presence, having served as editor-in-chief of the SIAM Journal on Computing between 1998 and 2003. His academic standing is reflected in his memberships within the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences, and the Academia Europaea. His awards include the 2005 Knuth Prize and the 2023 John von Neumann Theory Prize.
Fast facts
- Born: 1953, Athens, Greece
- PhD: Princeton University, 1979
- Knuth Prize: 2005
- John von Neumann Theory Prize: 2023
- ACM Fellow: 1998
- Citizenship: United States; Greece
- Languages: Modern Greek
Questions readers ask
What is the Yannakakis algorithm?
It is a method used for executing acyclic conjunctive queries in database systems, allowing them to be solved in polynomial time.
Which institutions has Yannakakis been affiliated with?
He has worked at Bell Laboratories, Avaya Laboratories, Stanford University, and Columbia University.
Achievements
- Affiliated with Columbia University
- Educated at National Technical University of Athens and Princeton University
- Worked as computer scientist
.jpg)
