Mihalis Yannakakis

The recipient of the seventh Donald E. Knuth Prize is Prof. Mihalis Yannakakis of Columbia University for his astonishing breadth of contributions to theoretical computer science. Mihalis has made major contributions to computational complexity theory, database theory, computer-aided verification and testing, and algorithmic graph theory. His fundamental contributions to computational complexity theory include two key papers in the PCP theory of hardness of approximation --- the definition of the class max-SNP and the proofs of hardness of approximation of graph coloring and set cover. In database theory his far-reaching contributions include the initiation of the study of acyclic databases and of non-two-phase locking. In verification he is arguably the researcher most responsible for laying the rigorous algorithmic and complexity-theoretic foundations of the field. The prize committee for the seventh Donald E. Knuth Prize, consisting of Richard Ladner, Tom Leighton, Laci Lovasz, Gary Miller, Mike Paterson and Umesh Vazirani (chair), awards the prize to Mihalis Yannakakis for the significance, impact and astonishing breadth of his contributions to theoretical computer science.

Created by Wolfgang Bein, July 18, 2002.

Last updated Mon May 01 17:13:20 PDT 2006