Shubhangi Saraf (Photo: Matt Hintsa)
Shubhangi Saraf, an associate professor in the Faculty of Arts & Science’s departments of computer science and mathematics, is the 2023 recipient of the distinguished McLean Award.
The McLean Award is funded by the University of Toronto’s Connaught Fund and is given in support of basic research in physics, chemistry, computer science, mathematics, engineering sciences or statistical sciences. It is awarded to an outstanding researcher early in their career to assist in attracting and supporting graduate students and post-doctoral fellows as part of their research team.
Saraf’s work brings together diverse areas of mathematics, allowing her to produce cutting-edge research that addresses some of the most challenging and fundamental questions in theoretical computer science.
Her primary research area is complexity theory, which studies the power and limitations of efficient computation. Saraf explains that some of the very fundamental questions are still far from being understood. “Is verifying a proof computationally much easier than finding one? What are the minimal amounts of computational resources needed for solving some natural computational tasks? How much does randomness really help in algorithms and computation? My research uses tools from mathematics to further our understanding of these questions,” she notes.
One of Saraf’s major research projects addresses the VP vs. VNP question, a foundational question of algebraic complexity theory and one that has remained open for over 40 years. It is the algebraic analog of the famous unsolved P vs. NP question, which asks whether every problem whose solution can be quickly verified can also be quickly solved.
To prove P is not equal to NP one needs to show that a certain rich class of problems (those whose solution can be quickly verified) cannot be solved efficiently. Similarly, to prove VP is not equal to VNP (and this is a prerequisite to proving P is not equal to NP), one needs to show that a certain rich class of problems cannot be solved efficiently using algebraic algorithms. Research from Saraf and her students has deepened our understanding of the potential and limitations of algebraic algorithms and brought researchers closer to resolving the VP vs. VNP question.
In addition to her contributions to complexity theory, Saraf is also highly regarded for her work in error correcting codes. Error correcting codes give a method for encoding data for storage and communication in a way that makes it resilient to errors.
“I feel deeply honoured and also incredibly grateful for the award and for the support from my colleagues,” says Saraf. “Areas such as mathematics and the theoretical foundations of computer science usually have only limited sources of funding. The McLean Award would greatly help in enabling and advancing the growth of junior researchers in my field.”
“Through her rigorous research and outstanding record of achievement, Shubhangi Saraf is advancing our understanding of open questions in computer science and mathematics, such as the power and limitations of efficient computation,” says Leah Cowen, U of T’s vice-president, research and innovation, and strategic initiatives. “The insights she harnesses from both computing and mathematics demonstrate the power and impact of interdisciplinary research.”
“The University of Toronto congratulates her on this important recognition of her work.”
Saraf adds the McLean Award to a list of honours that includes a Sloan Fellowship, an NSF Career Award and an NSERC Discovery Grant.
“My research is at the interface of math and computer science and uses ideas and inspiration from both fields. I’m especially delighted to be part of both communities at U of T.”