Media Releases

U of T computer scientist receives international award for pushing frontiers of knowledge

January 12, 2016

Toron­to, ON — Stephen Cook has won the pres­ti­gious BBVA Foun­da­tion Fron­tiers of Knowl­edge Award in the Infor­ma­tion and Com­mu­ni­ca­tion Tech­nolo­gies cat­e­go­ry for his pio­neer­ing and influ­en­tial work on com­pu­ta­tion­al com­plex­i­ty.

A Uni­ver­si­ty Pro­fes­sor Emer­i­tus, Cook said he is “aston­ished” and “delight­ed” by the award. In his long career, he has been fas­ci­nat­ed to see how “com­put­er sci­ence has advanced in leaps and bounds.”

World-renowned research

  • Cook expand­ed on Turing’s con­cept of com­putabil­i­ty – what a com­put­er can and can­not solve – to include effi­cien­cy, so we can ascer­tain which prob­lems are worth try­ing to solve and which are not
  • He defined a class of “hard­est prob­lems”, termed NP-com­plete, such that solv­ing one effi­cient­ly would mean all oth­er NP prob­lems were sim­i­lar­ly solv­able. “If you can show that a prob­lem is NP-com­plete, then very like­ly you should give up try­ing to solve it,” Cook said.
  • Cook is author of one of the Mil­len­ni­um Prob­lems; one, con­crete­ly, whose solu­tion touch­es on the encryp­tion and secu­ri­ty sys­tems under­pin­ning the dig­i­tal econ­o­my

“Steve’s con­tri­bu­tions to research and teach­ing are exem­plary, to say the least,” said Pro­fes­sor Ravin Bal­akr­ish­nan, chair of the depart­ment of com­put­er sci­ence. “His work has had glob­al impact and the fun­da­men­tal results of his decades of research con­tin­ue to be at the absolute fore­front of the­o­ret­i­cal com­put­er sci­ence.”

Seminal Paper presented in 1971

Cook’s sem­i­nal paper on the com­plex­i­ty of the­o­rem-prov­ing pro­ce­dures was pre­sent­ed in 1971, soon after he joined U of T’s new­ly cre­at­ed depart­ment of com­put­er sci­ence.

The paper had a tremen­dous impact on how sci­en­tists think about which prob­lems can be com­pu­ta­tion­al­ly solved in a rea­son­able amount of time and Cook’s pre­sen­ta­tion has been described as one of those rare moments when the sci­en­tif­ic world agrees the world has changed.

His cen­tral achieve­ment was to iden­ti­fy a sub-class of NP prob­lems which he termed NP-com­plete, whose dis­tin­guish­ing fea­tures are, first­ly, that they are the hard­est and, sec­ond­ly, that they are com­pu­ta­tion­al­ly equiv­a­lent: find­ing an effi­cient algo­rithm for one would yield algo­rithms for all the rest, and not just for the sub-set of NP-com­plete prob­lems, but for NP prob­lems as a whole.

“There are prob­lems that a com­put­er could fea­si­bly solve, except that it would take until the sun burns out,” Cook said. “These are prob­lems of the class we call NP. And then we have the class that we call P, which can be solved with­in an accept­able time frame. The trick is to decide which prob­lems are NP [not effi­cient­ly solv­able], and which are P [eas­i­ly solv­able].”

Fundamental Problems in Computer Science

Cook has also made fun­da­men­tal con­tri­bu­tions to com­pu­ta­tion­al the­o­ry, algo­rithm design, pro­gram­ming lan­guages and math­e­mat­i­cal log­ic, and his still-grow­ing body of work is like­ly to be cit­ed for many decades to come. He received an A.M. Tur­ing Award, the high­est hon­our for a researcher in com­put­er sci­ence, and his inquiries are now among the essen­tial the­o­ret­i­cal results that all com­put­er sci­ence grad­u­ates must under­stand.

Cook received the NSERC Ger­hard Herzberg Cana­da Gold Medal for Sci­ence and Engi­neer­ing in 2012. He is an Offi­cer to the Order of Cana­da, a fel­low of the Roy­al Soci­ety of Lon­don and the Roy­al Soci­ety of Cana­da, and was award­ed the Order of Ontario. Cook has also been elect­ed to mem­ber­ship in the Nation­al Acad­e­my of Sci­ences (Unit­ed States) and the Amer­i­can Acad­e­my of Arts and Sci­ences.

Acclaimed teacher

A very pop­u­lar and effec­tive teacher – cur­rent­ly teach­ing an under­grad­u­ate course on com­pu­ta­tion­al com­plex­i­ty and com­putabil­i­ty – Cook is also known as an excel­lent advi­sor and over­all leader with­in the math­e­mat­i­cal and com­put­er sci­ence com­mu­ni­ties.

photo of Stephen Cook teaching(pho­to above cour­tesy NSERC)

The BBVA Fron­tiers of Knowl­edge Award rec­og­nizes those who push back the fron­tiers of the known world by pos­ing rad­i­cal­ly inno­v­a­tive ques­tions that have led to new knowl­edge and sur­pris­ing pos­si­bil­i­ties.  Prizes are award­ed annu­al­ly in eight cat­e­gories:

  • Basic Sci­ences
  • Bio­med­i­cine
  • Ecol­o­gy & Con­ser­va­tion Biol­o­gy
  • Infor­ma­tion & Com­mu­ni­ca­tion Tech­nolo­gies
  • Eco­nom­ics
  • Finance and Man­age­ment
  • Con­tem­po­rary Music
  • Cli­mate Change & Devel­op­ment Coop­er­a­tion

 ‑30-

For more infor­ma­tion, con­tact:

Kim Luke
Direc­tor, Com­mu­ni­ca­tions
Arts & Sci­ence
kim.luke@utoronto.ca
416–978-4352

Nina Haikara
Senior Com­mu­ni­ca­tions & Exter­nal Rela­tions Offi­cer
Depart­ment of Com­put­er Sci­ence
Office: 416–978-3619
nhaikara@cs.toronto.edu
http://web.cs.toronto.edu/