Toniann Pitassi
Appointment
Canada CIFAR AI Chair (on leave)
Pan-Canadian AI Strategy
About
Appointed Canada CIFAR AI Chair – 2019
Toniann Pitassi is a Canada CIFAR AI Chair at the Vector Institute, and a professor in the department of computer science with a joint appointment in mathematics at the University of Toronto. She is also a Bell Canada Chair in Information Systems.
Pitassi’s primary research area is computational complexity, to understand which computational problems can be solved efficiently, and to develop the most efficient, least costly algorithms for such problems. Efficiency and cost is measured in terms of three computational resources: time, space, and randomness. Her research goal is to understand how much of these resources are required to solve important computational problems, and to understand the relationships and tradeoffs between the resources. The most famous problem in the area, the P versus NP problem, is the driving force behind much of her research. Her work also focuses on fairness in artificial intelligence and how to address biased data sources.
Awards
- Research Award, EATCS, 2021
- ACM Fellow, 2019
- Institute for Advanced Study (Princeton) Long-term member (5 years, 2017-22)
- European Association of Theoretical Computer Science Dissertation Award to her students, (2015, 2017)
- ACM Best Article, 2015
Relevant Publications
- Imagliazzo, R., Lei, R., Pitassi, T., and Sorrell, J. (2022). Reproducibility in Machine Learning. Symposium on Theory of Computing.
- Pitassi, T., Shirley, M., and Watson, T. (2021). Nondeterministic and Randomized Hierarchies in Communication Complexity. Computational Complexity, 30(2): 10.
- Fleming, N., Pankratov, D., Pitassi, T., and Robere, R. (2020). Random O(log n)-CNFs are Hard for Cutting Planes. Journal of the ACM (JACM).
Madras, D., Creager, E., Pitassi, T., & Zemel, R. (2019). Fairness through causal awareness: Learning causal latent-variable models for biased data. In Proceedings of the conference on fairness, accountability, and transparency (pp. 349-358).
Beame, P., & Pitassi, T. (2001). Propositional Proof complexity: Past, Present. Future, 42-70.
Pitassi, T., Beame, P., & Impagliazzo, R. (1993). Exponential lower bounds for the pigeonhole principle. Computational complexity, 3(2), 97-140.