Cheriton School of Computer Science Professor Eric Blais is one of nine researchers at the University of Waterloo to receive funding from the Ontario Ministry of Colleges and Universities through the Early Researcher Awards program.
Professor Blais, whose research interests span theoretical computer science with a special focus on sublinear-time algorithms, randomness in computation, and complexity theory, was awarded $140,000 in funding through the ERA program for his proposal titled “Sublinear-time algorithms for high-dimensional sets.” This funding amount is matched by an additional $50,000 by the University of Waterloo, bringing the total to $190,000.
“A central goal of computer science is to design efficient algorithms to solve fundamental computational tasks,” Professor Blais said. “Historically, algorithms that run in time proportional to the size of their input have been considered efficient. But for many modern massive datasets, the only practical algorithms are those that run in significantly less time than it takes to read their entire input.” Sublinear-time algorithms are one class of such algorithms. Over the past quarter of a century, computer scientists have successfully developed sublinear-time algorithms for computational tasks where the input is a large graph or a Boolean function, and the resulting algorithms have found multiple applications in the analysis of massive datasets.
“Many other massive datasets, however, can’t be modelled as graphs or Boolean functions,” Professor Blais explains. “To handle such datasets, we need to develop sublinear-time algorithms for a different type of input — what are known as high-dimensional geometric datasets. This is what my team of graduate students and I propose to do.” This work will develop new theoretical foundations for sublinear-time algorithms, advance our understanding of the nature of computation, and also lead to new algorithm design techniques for the software industry.
“Congratulations to Eric on receiving an Early Researcher Award,” said Raouf Boutaba, Professor and Director of the Cheriton School of Computer Science. “The impact of the research that Eric and his graduate students will conduct funded by this award will not only enhance Ontario’s stature in the international academic community, but it will also provide long-term economic benefits across the software industry.”
The research made possible through ERA funding will be structured to encourage collaboration among graduate students in the Cheriton School of Computer Science’s algorithms and complexity group. In particular, the training and guidance provided by Professor Blais and other faculty members in the algorithms and complexity group will enable a doctoral candidate to develop mentoring skills while working with two master’s students and several undergraduate researchers.
