Mihalis Yannakakis

Biosketch

Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science at Columbia University. He received his Diploma in Electrical Engineering from the National Technical University of Athens in 1975, and his PhD in Computer Science from Princeton University in 1979. He worked at Bell Laboratories as a Research Staff Member (1978-1991) and as Head of the Computing Principles Research Department (1991-2001), at Avaya Labs (2001-2002), and was Professor of Computer Science at Stanford University (2002-2003), before joining Columbia in 2004. Yannakakis is a member of the National Academy of Sciences, the National Academy of Engineering, and of Academia Europaea. He is a recipient of the Knuth Prize, a Fellow of the Association for Computing Machinery, and a Bell Labs Fellow.

Research Interests

Mihalis Yannakakis works in theoretical computer science, broadly interpreted. It includes work both in the foundations of computing (complexity theory and algorithms), as well as application of theory and algorithms to different areas of computer science and other fields. The general goals of the work in core theory are to capture formally basic computational phenomena in the form of complexity classes, study their relationships, and to develop efficient algorithms and characterize the computational complexity of fundamental problems. In optimization, one area of research concerns the approximation of hard combinatorial optimization problems, with the goal of developing methods to compute efficiently near-optimal solutions, and to characterize the limits of approximability. Other areas of interest include algorithmic game theory (equilibria computation, stochastic games), database theory (query optimization, concurrency control), and formal modeling, verification and testing of reactive systems.