By Ian Gormely

August 12, 2021

“I can’t think of someone more deserving of the EATCS Award than Toni Pitassi. Beyond her incalculable contributions to fundamental computer science, Toni’s compassion and humanity have driven her to apply her considerable skills to creating a more equitable society. – Garth Gibson, Vector Institute President and CEO

There is a single overarching goal that guides Vector Faculty Affiliate Toni Pitassi across her 30-plus years in computer science: solving P versus NP, one of computer science’s major unsolved problems. “I don’t know if it’s attainable in my lifetime,” Pitassi concedes. 

The implication of the problem is significant. If P, a set of easy problems, were equal to NP, a set of very hard problems, many problems that appeared difficult would actually be solvable. However, most mathematicians do not believe this is the case. “You can spend many years and not really get anywhere. Like, how do you have a way of characterizing every single efficient algorithm and then ruling it out?”

Still, Pitassi notes, in pursuit of one problem, researchers will inevitably solve others. “We all chip away at it from different angles with different ideas,” she says. “In the process, the theory community has come up with many ideas and discoveries that lead to other, sometimes unexpected, breakthroughs.”

Though unanticipated, these research paths have not been in vain. She was recently selected as the 2021 recipient of the European Association for Theoretical Computer Science Award which acknowledges “extensive and widely recognized contributions to theoretical computer science over a life long scientific career.”

One so-called tangent that the Association singled out in decorating Pitassi was the lifting theorem she helped pioneer, noting that the theorem has completely transformed understanding of decision trees and communication complexity. The theorem “has been very successful in resolving many open problems” says Pitassi and “led to a much better understanding of the nature of computation in many restricted models.” But resolving P vs NP “will require more breakthroughs.”

Asked about the EATCS award and others like it, Pitassi demures. “I’m proud of some of the stuff I’ve done, but a lot of people deserve these kinds of awards,” she says. “I am happy that people took the time to write me the letters. It definitely makes me feel like I’m in a nice community of people that take time out of their lives.” 

That community is one forged over a long career that’s seen Pitassi zig-zag across the continent. American by birth, she received her PhD from the University of Toronto in 1992 before completing a postdoc at UC San Diego. She took her first faculty position at the University of Pittsburgh, followed by an opportunity at the University of Arizona, and finally, back to U of T where she is a professor in the Computer Science Department and a six year appointment at the Institute for Advanced Study. “I never thought we’d end up in Canada for good,” she says. But I felt so supported here. When it turned out the U of T had an opening, I was pretty excited.” 

In more recent years her work has taken her down another tangent: using technology to create a more equitable society. Specifically Pitassi is putting her formidable skills to developing frameworks and approaches that will identify and mitigate bias in machine learning algorithms. 

A technical solution to the problem is preferable to “political wins,” when it comes to problems like the distribution of wealth and equitable access to essential goods and services. Pitassi admits that such a simple goal is nevertheless lofty and finding a technical solution is as difficult as one based in public policy. “It’s even hard to formulate the question in a way that’s precise.” Of course, considering the rest of Pitassi’s career, it will be the effort and learning along the way that ultimately counts.