Home

Mihalis Yannakakis

PERCY K. AND VIDA L. W. HUDSON PROFESSOR OF COMPUTER SCIENCE

455 CS Building
Mail Code 0401

Tel(212) 939-7145
Emailmy2144@columbia.edu

Mihalis Yannakakis works on the theoretical foundations of computing, seeking to understand the inherent computational complexity of problems and to design efficient algorithms for their solution.  He has applied this principled algorithmic approach to problems from different areas.

Research Interests

Design and analysis of algorithms, computational complexity, algorithmic game theory, combinatorial optimization, database theory, modeling, verification and testing.

Research Areas

AlgorithmsComputing SystemsData ScienceSystemsConnected Humanity

Links

VISIT COMPUTER SCIENCEWEBSITECV
His activities include research in combinatorial optimization, developing efficient approximation a lgorithms for hard optimization problems, characterizing the limits of approximability, and investigating trade-offs in multicriteria optimization; in algorithmic game theory, studying the computation of equilibria for games and markets, and algorithms for pricing and mechanism design;  in modeling, verification and testing of reactive systems; in databases, in query processing and concurrency control.
 
Yannakakis received his Diploma in Electrical Engineering from the National Technical University of Athens, Greece in 1975, and his PhD in Computer Science from Princeton University in 1979.  He is a member of the National Academy of Engineering, of Academia Europaea, and of the National Academy of Sciences, a recipient of the Knuth Prize, a Fellow of the Association for Computing Machinery, and a Bell Labs Fellow. 

PROFESSIONAL EXPERIENCE
  • Percy K. and Vida L. W. Hudson Professor of Computer Science, Columbia University, 2004-
  • Professor of Computer Science, Stanford University, 2002–2003
  • Head, Computing Principles Research Department, Avaya Laboratories, 2001-2002
  • Head, Computing Principles Research Department, Bell Laboratories, 1991-2001
  • Member of Technical Staff, Computing Science Research Center, Bell Laboratories, 1978-1991

PROFESSIONAL AFFILIATIONS
  • Association for Computing Machinery (ACM)

HONORS & AWARDS
  • Member, National Academy of Sciences, 2018
  • Member, Academia Europaea, 2013
  • Member, National Academy of Engineering, 2011
  • Knuth Prize, 2005
  • Fellow, Association for Computing Machinery (ACM), 1998
  • Fellow, Bell Laboratories, 1997

SELECTED PUBLICATIONS
  • X. Chen, I. Diakonikolas, A. Orfanou, D. Paparas, X. Sun, M. Yannakakis, “On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms”, Proc. 56th IEEE Symp. on Foundations of Computer Science, 2015.
  • K. Etessami, M. Yannakakis, “Recursive Markov Decision Processes and Recursive Stochastic Games,” Journal of ACM, 62(2):11, 2015.
  • X. Chen, D. Paparas, M. Yannakakis, “The Complexity of Non-Monotone Markets,” Proc. 45th ACM Symp. on Theory of Computing, pp. 181-190, 2013.
  • K. Etessami, M. Yannakakis, “On the Complexity of Nash Equilibria and Other Fixed Points,” SIAM J. on Computing, 39(6), pp. 2531-2597, 2010.
  • C. H. Papadimitriou, M. Yannakakis, “On the Approximability of Trade-Offs and Optimal Access of Web Sources,” Proc. 41st IEEE Symp. on Foundations of Computer Science, pp. 86-92, 2000.   
  • D. Lee, M. Yannakakis, “Principles and Methods of Testing Finite State Machines - A Survey,” Proceedings of the IEEE, 84 (8), pp. 1090-1126, 1996.
  • C. Courcoubetis, M. Yannakakis, “The Complexity of Probabilistic Verification,” Journal of ACM, 42(4), pp. 857-907, 1995.
  • C. Lund, M. Yannakakis, “On the Hardness of Approximating Minimization Problems,” Journal of ACM, 41(5), pp. 960-981, 1994.
  • C. H. Papadimitriou, M. Yannakakis, “Optimization, Approximation and Complexity Classes,” J. Computer and System Sciences, 43(3), pp. 425-440, 1991.
  • M. Yannakakis, “Expressing Combinatorial Optimization Problems by Linear Programs,” J. Computer and System Sciences, 43(3), pp. 441-466, 1991.
  • C. Beeri, R. Fagin, D. Maier, M. Yannakakis, “On the Desirability of Acyclic Database Schemes,” Journal of ACM, 30(3), pp. 479-513, 1983.