Department of Computer Science

University of Toronto

Research

Without doubt, Prof. Cook is the best known Computer Science researcher in Canada and amongst the very elite in the world. Through the course of his extraordinary 40- year career, Professor Steve Cook has demonstrated excellence and impact on many aspects of theoretical computer science, on training of the next generation of Computer Scientists, and on the society as a whole. Cook also established the now famous P versus NP question as to whether or not every decision problem that is efficiently verifiable (in NP) can be made to be efficiently computable (in P) and conjectured (now known as Cook’s Hypothesis) that P does not equal NP. The P versus NP question is one of the seven million dollar “Millennium Prize Problems” listed by the Clay Mathematics Institute (www.claymath.org), and is widely considered to be among the top three, if not the top, open problems in mathematics today. He has continued as a major force in the evolution of Computational Complexity. In the 1980s, he laid down key ideas in the development of a solid theory of complexity of parallel computation. More recently, a major thrust of Dr. Cook’s work has been in formal logics, their relation to program semantics, and their application to the notion of succinct proofs. In particular, he started the research field of proof complexity.

Teaching

Cook is a spectacular teacher, an excellent advisor, and an overall leader within the mathematical and computer science communities. He has advised many of the best PhD students and postdocs in theoretical computer science in the world. Out of Prof. Cook’s 29 Ph.D. students (and counting), most have gone on to highly successful careers of their own, obtaining positions in some of the most prestigious universities worldwide.

Recognition

Cook holds the only Turing award in Canada, awarded to him in 1982. He is also a member of the American Academy of Arts and Science, the Royal Society of Canada, the Royal Society (London), the National Academy of Sciences (United States). He is the recipient of the NSERC Research Excellence Award, winner of the Royal Society of Canada’s John L. Synge Award, and a holder of a variety of other prizes and honors. He was also recently elected as Member of the Order of Ontario and as Officer of the Order of Canada.