Toniann Pitassi is a computer scientist and mathematician specializing in computational complexity theory, and proof complexity, a branch of complexity theory that studies the complexity of mathematical proofs of logical propositions. Pitassi is also known for her foundational work in theoretical aspects of machine learning, including differential privacy, adaptive data analysis, and fairness. Pitassi was born in Pittsburgh and received BS and MS degrees in Computer Science and Chemistry from Penn State, and a PhD in Computer Science from the University of Toronto. After a postdoc at UCSD and faculty positions at University of Pittsburgh (Mathematics) and University of Arizona (Computer Science), she joined the University of Toronto (Computer Science) from 2000-2021. Pitassi joined the computer science department at Columbia University in 2021 and was also a member of the Institute for Advanced Studies (Mathematics) from 2016-2022.

Research Interests

Toniann Pitassi's primary research is in computational complexity, which aims to understand the inherent time and space required to compute fundamental problems in computer science. She is particularly interested in proof complexity, a branch of complexity theory that aims to prove upper and lower bounds on the lengths of proofs of logical propositions in well-studied proof systems. Pitassi uses tools from logic, combinatorics, and communication complexity, the study of the amount of information that must be communicated by two or more parties in order to compute a joint function of their inputs. Pitassi and her collaborators have resolved several open problems in these areas by developing new lower bound approaches. Pitassi is also recognized for her research on foundational aspects of machine learning, including privacy, fairness, adaptive data reuse, and most recently a mathematical framework for reproducible machine learning.

Membership Type


Election Year


Primary Section

Section 34: Computer and Information Sciences

Secondary Section

Section 11: Mathematics