Chris Trevisan, a fourth-year computer science student, is one of eight recipients — and the only recipient from a Canadian university — to receive the 2025 Computing Research Association Outstanding Undergraduate Researcher Award. The association’s top recognition honours exceptional undergraduate students from universities across North America who demonstrate outstanding research potential in the field of computing.
“Chris is a truly exceptional undergraduate researcher,” said Professor Gautam Kamath, one of two Cheriton School of Computer Science faculty members who supervised his research. “He independently solved a challenging mathematical research problem and authored a paper that was accepted at the 2024 Symposium on Discrete Algorithms, among the top conferences in algorithm design and discrete mathematics. His paper was the only one at SODA 2024 presented by a sole undergraduate author. Chris is the second person from Waterloo to ever win the top prize, joining Elyot Grant, who received the CRA Outstanding Undergraduate Researcher Award in 2010.”
Sponsored this year by Sandia National Laboratories and Lawrence Berkeley National Laboratory, the CRA Outstanding Undergraduate Researcher Award highlights the impact of groundbreaking work by undergraduate researchers.
Professor Sepehr Assadi, who also supervises Chris’s research, describes his experience working with him. “I got to know Chris when I attended his talk at SODA 2024 and I was blown away both by his superb presentation and the depth and breadth of his results,” said Professor Assadi. “I invited Chris to join a research project with me, working on a notoriously challenging open question in theoretical computer science and extremal graph theory. It has been a great pleasure working with Chris and I’m quite hopeful that with his outstanding technical and research skills we will be able to make significant progress on this longstanding open problem.”
Chris Trevisan is in the final year of his undergraduate studies in computer science, but his interest in the discipline can be traced back before his time at Waterloo. While attending William Lyon Mackenzie Collegiate Institute in Toronto, Chris won two silver medals at the International Olympiad in Informatics, the world’s most prestigious computer science competition for secondary school students. After enrolling at Waterloo, he continued to excel in algorithmic problem-solving and represented the university in various International Collegiate Programming Contests. In April 2024, he was one of three exceptional algorithmic programmers representing Waterloo at the 46th ICPC World Finals in Luxor, Egypt, where the team was the top-ranked competitor from a Canadian university.
More about Chris Trevisan’s SODA 2024 paper
Sorting and selection are fundamental problems in computer science. Given a list of numbers, either place them in order from least to greatest (sorting) or output the element that would be in the kth position of a sorted list (selection). Variations of the setting with certain modified constraints, however, cause the structure of the problem to change dramatically, resulting in much more interesting algorithmic problems.
For example, sorting and selection of numbers can be done under the adversarial comparator model, where comparisons can be adversarially tampered with. Usually, one can compare two numbers and learn which of the two elements is greater. But in the adversarial model, if the values of the two elements are close to one another, the comparison may give the incorrect answer. Another constraint one can consider is parallelism — in other words, how many rounds of adaptivity are needed to perform sorting or selection, sometimes called sorting and selection in rounds, which explores the trade-off between accuracy, number of comparisons, and number of rounds. If one can specify all the comparisons in advance, the algorithm is non-adaptive. Otherwise, if the comparisons that must be done depend on the results of previous comparisons the algorithm is adaptive.
Chris’s SODA paper resolves several classic open problems in the area, and provides a number of interesting new algorithms. Some of his main results are improved algorithms for adversarial sorting and selection, which show surprising gaps on the power of randomness for this problem. He also has more sophisticated results that additionally minimize the round complexity of the problem. Techniques range from careful structural and probabilistic analyses of text-book algorithms to more advanced techniques like sorting networks.
To learn more about the research that led to Chris receiving a 2025 CRA Outstanding Undergraduate Researcher Award, please read his paper, Sorting and Selection in Rounds with Adversarial Comparisons, presented at the 2024 Symposium on Discrete Algorithms (SODA).