David R. Cheriton School of Computer Science 50th Anniversary

Research Excellence

Davis Centre at University of Waterloo

Some of the most interesting transformative research happening in the David R. Cheriton School of Computer Science at the University of Waterloo hasn’t come to public attention, or even to fruition.


But you have to presume that it will happen, in a School and in a University that’s already done so much to transform our society.

For instance, think about the smartphone in your hand, or in your pocket. An early smartphone, the BlackBerry, was born in Waterloo. Michael Lazaridis, a former Waterloo Engineering and Computer Science student, kicked off the smartphone revolution. In doing so, he completely changed the way we communicate with each other.

“It’s amazing how many people use computing these days, between the Web and iPhones and other cell phones and social media, and it’s all being driven by computers and computer applications,” said Frank Tompa, a Distinguished Professor Emeritus in the Cheriton School of Computer Science. “And yet so many people think that they’re not interested at all in computing, or in advancing computing.

“It’s hard sometimes to convince people that computer science is something worth studying, even though it is so universally applicable. And everybody who works in computer science can make a contribution that a lot of people will care about.”

Tompa would know. His work in the 1980s to digitize the Oxford English Dictionary resulted in the development of a search engine that led not only to the creation of the spinoff company OpenText Corporation, but also, whether directly or indirectly, to a lot of things that we can now do every day on the Internet.

And breakthroughs like this happen all the time, said Stephen Watt, the Dean of the Faculty of Mathematics. Watt helped to create the Maple computer algebra system in the early and mid 1980s while he was a graduate student at the Cheriton School of Computer Science.

“We’re in an interesting golden age of computing. It’s not so much about where we put the resistors any more. It’s about how we deal with information and the ultimate capabilities of computation,” Watt said. “Things that used to be only theoretical results in computer science are now really practical necessities.

“For example, in the area of computer algebra, the idea of asymptotically fast algorithms and working with very high degrees of parallelism, for decades these were just theoretical curiosities in the larger picture of things. They were very interesting and important research questions, but they didn’t have an impact on day-to-day life. Now, in a professional grade piece of computer algebra software, you must have asymptotically fast algorithms, and you must be making use of multiple processors. That ability to have the natural continuum from mathematics through theoretical computing to the practice of computing, we’re very fortunate to be able to do that in a Faculty of Mathematics.”

So what might we expect from ongoing computer science research at Waterloo?

Lazaridis now devotes his knowledge and financial investment to the study of quantum computing, which is one of 16 distinct research areas within the Cheriton School of Computer Science. He’s invested $200 million in the Institute for Quantum Computing (IQC).

Computer Science is among seven different academic units represented in the IQC. John Watrous, a member of the IQC and a professor in the Cheriton School of Computer Science, said he enjoys the opportunity to work with colleagues not only in other departments within the Faculty of Mathematics – Applied Mathematics, Pure Mathematics, and Combinatorics and Optimization – but also in Electrical Engineering, Chemistry, and Physics.

“Twenty years ago it was pretty difficult to talk about these things, people not really understanding what one another was saying,” he said, noting that Shor’s algorithm, formulated in 1994, was the impetus for collaboration across departments and faculties at universities interested in quantum computing. “It took a while for physicists and computer scientists to be able to speak to one another at a meaningful level, where they really were understanding.

“There’s very different ways of approaching the disciplines. Computer scientists tend to build things; we want to do things that have a utility. We want to design algorithms or protocols for doing things, whereas physicists are more interested in explaining the things that happen in the natural world. I think it was interesting to see that process taking place, and now computer scientists are publishing papers in physics journals, and physicists are publishing papers in computer science conferences. There’s a lot of collaboration, and it’s interesting to see it happen. But it took time.”

Quantum complexity

The theory behind quantum computing research is that because a quantum system can be in multiple states at the same time, quantum computers will be able to simultaneously process an immense number of calculations – something that’s far beyond the scope of computers as we know them.

“We don’t have quantum computers that we can use and run things on. We have very small experiments,” Watrous said. “But that physical model, quantum mechanics, is incredibly accurate. It’s never been refuted.

“It’s mysterious, and people sort of play up this mystery because they want to make people fascinated by quantum mechanics, but if you ignore the strangeness of it, it isn’t that complicated. It’s just linear algebra; the mathematics of it is not that complicated.”

Similarly, Srinivasan Keshav also works to apply mathematical techniques to his computing research. The computer networking expert now focuses his efforts on energy systems – specifically, the smart grid.

“At a fundamental level, moving electrons and moving bits is pretty similar,” said Professor Keshav, “so there’s been a whole slew of computer networking researchers who have started working in the area of electricity or energy.

“The Internet moves bits packets, and the electricity grid moves electrons. . . You can think of electrons as negative bits. Instead of consuming information at a variable rate, you generate power at a variable rate, but the math is the same. You can take all the math that was used for building the Internet 20 years ago, and you can convert it into managing the electrical grid. It’s a very cool idea.”

Keshav has held the Cisco Canada Research Chair in Smart Grid since 2012. He’s one of few computer scientists taking an active role in this field, and he feels like society is ready for more people to step up and begin working on it.

“Five years ago, if you wanted to buy an electric car, what were your choices? Nothing. Do you know how many electric cars are available in the market in Ontario today? Thirty-seven models,” he said. “The mind-shift has changed in people.

“Solar is everywhere, and five years from now in Ontario there will be solar panels everywhere as well. The price of solar panels has gone way down. It’s gone from $76 a watt to about 40 cents a watt in the last 30 years. It’s very similar to the decrease in price of microprocessors.”

And that’s why Keshav believes it’s natural that more people will continue to choose alternative sources of energy. This will in turn result in more and better research, leading to continued improvements and cost savings.

“It’s like this big revolution going on – you can see it. You can see that solar panels are coming, you hear that Elon Musk is leading this charge, you hear about wind energy,” he said. “Energy transformation to me is the foundation for not just my work, but it’s going to be the foundation for a whole generation of researchers.”

A big challenge for researchers like Keshav is figuring out how the grid can best handle variable electricity generation. The province phased out coal-fired generation, which offered a constant source of power even if it wasn’t necessarily good for the environment.

But constant power generation is not possible with solar and wind, which of course vary depending on weather conditions. Researchers are working to solve that problem with better storage capabilities.

“I won’t say it’s transforming society just yet. I think it’s trying to. The potential is there,” Keshav said of his work. “Honestly, most research is a crapshoot. You pick what you hope is an important problem, you do your best to work on it, and how it works out is, I would say, as much chance as it is planning.

“If it happens, it might happen five, 10 years from now. It’s hard to tell,” he said. “Fingers crossed.”

And while he waits for that breakthrough, Keshav remembers why this type of work is important to him.

“Researchers in academia are very privileged in the sense that we have very few demands on our output. We are, by and large, free to choose our own research areas,” he said. “And with that freedom comes responsibility. That responsibility, in my mind, is to attempt to make a positive contribution to society, which is very generously funding us.

“I believe that the kind of problems I want to solve are the problems on the front pages of newspapers. That’s why I always try to work on socially relevant problems, relevant to society on a broader scale – energy, water, infrastructure.”

Windmill solar

Research done at the Cheriton School of Computer Science is nationally and internationally recognized, and so is its faculty.

The Canadian Association of Computer Science has named Outstanding Young Computer Science Researchers annually since 2009, and five professors from the Cheriton School have been so honoured: Bin Ma, Ian Goldberg, Ondřej Lhoták, Kate Larson, and Lap Chi Lau.

The award recognizes excellence in research by a professor who is within 10 years of completing their PhD. For Professor Larson, it was the second significant prize she has received in recent years, having also won an Early Researcher Award from the Ontario Ministry of Research and Innovation.

“It’s lovely to get awards,” she said, “but it reflects nicely back on the School. The School’s given me a lot, and been very, very supportive for me to pursue whatever research questions I’ve found interesting. They let me do whatever I want, and just work on whatever projects I want.”

Larson’s areas of interest are at the intersection of artificial intelligence, game theory, and microeconomics. She has a focus on strategic reasoning in computational settings, and is fascinated by problems that arise when different users of a system, often fueled by competition for resources, demonstrate opposing preferences in terms of potential outcomes.

“It lends itself naturally to a variety of applications, whether it’s more of an economics-markets base, or maybe it’s in support of group decision-making, or maybe it’s allocating resources in different contexts,” she said.

“For example, I’ve done work with forest fire fighting and resource allocation problems there, or in how do you hire crowd-sourcing workers to ensure you get good outcomes in the end? They all have this tie-in where there’s this limited resource and conflicting preferences, and so how do we reason and design systems for those cases?”

Larson acknowledged with a laugh that her research might not easily be understood. But it is practical and transformative, and, most importantly, it’s supported by her colleagues and by the Cheriton School of Computer Science.

“Sometimes I’ll give presentations and half the audience is thinking, ‘What in the world is she talking about?’” she said. “But they’ve always been happy to let me run with whatever I wanted, whatever I thought was interesting and looked promising.”

That’s true also of research that’s done more or less for fun. Dan Brown, a professor whose area of interest is Bioinformatics, managed to pivot from the Human Genome Project to work in music information retrieval.

“I always wanted to adapt some of the techniques we’d used (in the Human Genome Project) to pattern matching in music,” said Brown, who found an undergraduate student in the Bioinformatics program who was interested in the same thing – but with a twist. The student, Hussein Hirjee, suggested they work on rap music. Brown didn’t like rap music, and didn’t believe it would work in this context.

But Hirjee played an Eminem and Jay-Z song called “Renegade,” and Brown immediately recognized its lyrical complexity. They ended up writing an algorithm that could find rhymes in raps and characterize them. It could identify rappers by their signature techniques, and it could even identify ghostwritten songs.

Dan Brown

“I was astonished at how good it was, but it actually works,” Brown said of the algorithm. “We could predict which artist was responsible for those lyrics more than half the time out of a collection of about 25. . . There’s a Dr. Dre song called ‘Still D.R.E.’ that Jay-Z actually wrote; our program calls it a Jay-Z song.”

A related project focused on misheard lyrics in songs – mondegreens, they’re called. When Hirjee and Brown presented this work at the International Society for Music Information Retrieval Conference in 2010, Hirjee won the Best Student Paper Award. He received his master’s degree that same year after presenting a thesis that used probabilistic methods to analyze hip-hop, poetry, and misheard lyrics. Now an MD and a resident in psychiatry, Hirjee has since co-authored a paper on music therapy in patients with dementia and behavioural disturbance.

Brown, meanwhile, later teamed up with another student and used the earlier complexity measure to predict whether certain songs would become hits.

“Hit songs are more complex in their rhyme patterns than flops,” he said. “What we’re really actually detecting when we’re looking for complexity in the rhyme patterns is craft. Somebody actually cared enough about it to have a little wordplay, have a little teasing of something where, if you were just reading the lyrics, you would smile here and there.”

Such work is possible because the Cheriton School of Computer Science demonstrates faith in its researchers to devote their energy to work of their choosing, as long as it’s in the wide-ranging field of computer science.

“I can go off and work on making computers write poetry, and have them analyzing song lyrics, and applying techniques from biology to other fields, treating questions in basic biology as if they were math problems, and solving them,” Brown said. “Or working with people on reducing the harms of casino gambling, which is a field I’ve done a lot of work on in the last few years.

“I’ve taken real advantage of that, and that’s been a real joy of being here at Waterloo.”

It’s the joy and the quest for answers that also motivates John Watrous as he continues to investigate quantum computing and the potential of building a quantum computer. He truly loves his work, even if a breakthrough in the field isn’t necessarily imminent.

He acknowledged that it might not happen in his lifetime, or at all. He’s also wondered – if it does happen, what if there’s no practical value to it?

“We don’t really know if this is going to be truly useful or commercial, or, if it is, what form it will take,” he said. “There is a potential there. . . and I think it makes sense to investigate it. If nothing else, it’s keeping me off the street.

“I do think the scientific method is on our side. The models say this should work, and we need to investigate that possibility.”

And if the possibility turns out to be false and the models don’t work, Watrous said that’s an outcome he and other researchers are prepared to accept.

“I would be just as happy proving some mathematical result that would establish an impossibility for quantum computing,” he said. “There’s one reality. Something is true. I want to know what’s true. I want to know what’s real. And if it turns out that quantum computers cannot be built for some fundamental reason, of course I want to discover that.

“Would I just bury that and say, let’s just keep pretending? No, I’ll sink the whole ship if I get the chance. But that would be not me deciding, that would be the reality of the world. It exists now, and I think we just want to know what this is. But we also want to do things with value.”

One thing he and his colleagues in the Cheriton School of Computer Science already know is that they’re in a place where the value they’re looking for can be found and shared. It’s the perfect research facility for them.

“You find a lot of energy at Waterloo, which doesn’t always exist at other universities,” Watrous said. “You’ll see people with this drive to get things done, and I think that’s an important part of the University.”