Mihalis Yannakakis

The central question in the theory of computation is the problem of complexity: why are some computational problems solvable by efficient algorithms while others seem to resist such solution?  Over the past four decades, Yannakakis has contributed as much as very few others to the understanding of both the question and its surprising extent, having resolved some of the hardest and most stubborn open problems but also opened new avenues of inquest: new modes of complexity and new areas of application, most notably program verification and microeconomics.  His work is extremely powerful technically, but also very broad and influential.