Computer scientist wins Canada's top science prize

A Toronto researcher who has dedicated his career to proving whether certain types of problems are solvable by computers has won this year's Gerhard Herzberg Canada Gold Medal for Science and Engineering, which comes with $1 million in research funding.

Canada's top annual science prizehas gone toStephen A. Cook, a researcher in the department of computer science at the University of Toronto.

"It's quite an honour, I have to say," Cook said in an interview hours before officially receiving the medal from Governor General David Johnston at a ceremony at Rideau Hall in Ottawa Wednesday afternoon.

'We're interested in whether the problems can be solved at all feasiblyin other words, before the sun expires.' Stephen Cook, University of Toronto

Cook's research focuses mainly on computational complexity and proof complexity, two areas of theoretical computer science and mathematics that involve figuring out how much time and memory it will take computers to solve different types of problems.

"In particular, we're interested in whether the problems can be solved at all feasiblyin other words, before the sun expires," he said.

That's important question for assessing how secure certain kinds of encryption actually are, such as the kind used by PayPal to send credit card information securely over the internet.

Cook notes that while the information is encrypted as it passes between your computer and PayPal's server, the encrypted data is publicly visible and interceptible by an eavesdropper.

"Paypal's computer knows how to decrypt it, but the assumption is the eavesdropper can't because it's computationally intractable," Cook said.

However, it hasn't yet been proven that the encryption scheme is unsolvable, so Cook and his colleagues are working to find out whether the assumption is actually true.

Funding for more thinkers

Cook said theprize money of $200,000 per year over five yearswill go towardssupporting graduate students and hiring postdoctoral fellows to collaborate with him and his colleagues in their research.

"We're theoreticians so we don't have big laboratory costs," he said. "We sit and think and consult and travel."

Cook was officially forced into mandatory retirement in 2005. However, he manages to continue to teach and conduct research full-time at the university under contract.

The Herzberg medal, named after the winner of 1971 Nobel Prize in Chemistry,recognizes researchers for excellence and "influence in research for a body of work conducted in Canada that has substantially advanced" their field.

According to a release from Canada's Natural Sciences and Engineering Research Council announcing the award, Cook's inquiries "are now among the most essential theoretical results that all computer science graduates must understand."

Cook wasthe 1982 winner of the Turing award, the top research honour in the field of computer science.

The Natural Sciences and Engineering Research Council has also announced the winners of several other top prizes, including the John C. Polanyi Award, which recognizes a "recent outstanding advance" in science or engineering. That went to University of Toronto chemist Greg Scholes.

Scholes receives a grant of up to $250,000 for his research on the role of quantum mechanics in photosynthesis.