July 04, 2023

Two students from the School of Computing Science received scholarship awards to help support their research projects.

MSc student Yi Chen was awarded the 2023 Canada Graduate Scholarships-Master’s (CGS M), while PhD student Halley Goldberg was presented with the Postgraduate Scholarship-Doctoral (PGS D) award.

Under the supervision of Eugenia Ternovska, Chen’s research falls under the field of logic, focusing on model-checking and satisfying problems. Currently in a place of identifying the decidable fragments of these problems, they can possibly derandomize some classes of randomized algorithms. The key to their research is in the design of their new logic, the novelty of which presents another way to study randomized algorithms. Chen supports Ternovska by studying fundamental problems in this newly designed structure.

The 2023 Canada Graduate Scholarships-Master’s (CGS M) award will help Chen continue this work that can potentially introduce more unobserved classes of algorithms, which may be useful theoretically. The award is presented by the Canadian Institutes of Health Research (CIHR) in partnership with the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Social Sciences and Humanities Research Council of Canada (SSHRC). This scholarship is awarded to students who have displayed a high level of achievement in their graduate studies.

“It is my honor to achieve this award, and I am very thankful to my supervisor Eugenia,” says Chen. “She has helped me so much with the research and with the award application.”

As for Goldberg, her research is in computational complexity theory under the supervision of Valentine Kabanets. They are exploring the “meta-complexity” of measures such as circuit size and Kolmogorov complexity, particularly showing some connections to learning theory and average-case complexity. “Meta-complexity” refers to the computational complexity of problems which are themselves asking about complexity. In recent years, this approach has yielded exciting progress in a number of seemingly unrelated areas of computer science theory.

“I would say that the ultimate goal of our work is to better understand what is minimally required of a model of computation for it to support important tasks such as learning and cryptography, as well as elucidating relationships and dichotomies between these areas,” says Goldberg.