Toniann Pitassi is a Canadian-American mathematician and computer scientist who focuses on computational complexity theory. She is currently the Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University. Previously, she held the Bell Research Chair position at the University of Toronto.

Academic career

Pitassi, who was born in Pittsburgh, received her bachelor's and master's degrees from Pennsylvania State University. She then moved to the University of Toronto to complete her doctoral studies and earned her PhD in 1992 under the guidance of Stephen Cook. After finishing her PhD, she worked on research at the University of California, San Diego, and held teaching positions at the University of Pittsburgh and the University of Arizona. In 2001, she returned to Toronto and worked as a professor in the University of Toronto Department of Computer Science and the University of Toronto Department of Mathematics until 2021, when she joined Columbia University as a faculty member.

She spoke at the International Congress of Mathematicians in Berlin in 1998. She led the program for the 2012 Symposium on Theory of Computing. From September to December 2017, she was a visiting professor at the Institute for Advanced Study.

Research

Pitassi's research has mainly studied proof complexity, a part of computational complexity theory that looks for limits on how long mathematical proofs can be for logical statements in different proof systems. The purpose of this research is to understand how long it takes to find proofs and to compare the strengths of different proof systems.

Her work includes showing that certain proofs, like those for the pigeonhole principle using Frege proofs, require an extremely large number of steps. She also found similar results for the cutting-plane method when applied to problems related to the maximum clique, and for resolution proofs when solving dense random 3-satisfiability problems. Additionally, she showed that these same problems can be solved in less than exponential time using the Davis–Putnam algorithm. With other researchers, she has written articles and reviews about proof complexity overall, about algebraic proof complexity, and about semialgebraic proof complexity.

Recognition

In 2018, Pitassi was chosen as a member of the ACM Fellows for her work in research and teaching related to computational complexity and proof complexity. In 2021, she received the EATCS Award for her important and broad contributions to computational complexity. In 2022, she was elected to the National Academy of Sciences.

Selected publications

• Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell (1993). "Exponential lower bounds for the pigeonhole principle." Computational Complexity. 3 (2): 97–140. DOI: 10.1007/BF01200117. MR 1233662. S2CID 1046674.
• Beame, Paul; Pitassi, Toniann (1996). "Simplified and improved resolution lower bounds." Proceedings of the 37th Annual Symposium on Foundations of Computer Science. Pages 274–282. DOI: 10.1109/SFCS.1996.548486. ISBN 0-8186-7594-2. MR 1450625. S2CID 14341656.
• Bonet, Maria; Pitassi, Toniann; Raz, Ran (1997). "Lower bounds for cutting planes proofs with small coefficients." Journal of Symbolic Logic. 62 (3): 708–728. DOI: 10.2307/2275569. JSTOR 2275569. MR 1472120.
• Beame, Paul; Pitassi, Toniann (1998). "Propositional proof complexity: past, present, and future." Bulletin of the European Association for Theoretical Computer Science (65): 66–89. MR 1650939. Reprinted in Current Trends in Theoretical Computer Science. World Scientific, 2001. MR 1886033.
• Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael (1998). "On the complexity of unsatisfiability proofs for random k-CNF formulas." Proceedings of the 30th ACM Symposium on Theory of Computing. Pages 561–571. CiteSeerX 10.1.1.39.213. DOI: 10.1145/276698.276870. ISBN 0-89791-962-9. MR 1715604. S2CID 10262912.
• Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael (2002). "The efficiency of resolution and Davis-Putnam procedures." SIAM Journal on Computing. 31 (4): 1048–1075. DOI: 10.1137/S0097539700369156. MR 1919956.
• Dwork, Cynthia; Naor, Moni; Pitassi, Toniann; Rothblum, Guy N. (2010). "Differential privacy under continual observation." Proceedings of the forty-second ACM symposium on Theory of computing. Pages 715–724. DOI: 10.1145/1806689.1806787. ISBN 9781450300506. S2CID 1522154.
• Dwork, Cynthia; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Zemel, Richard (2012). "Fairness through awareness." Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ITCS '12. New York, NY, USA: ACM. Pages 214–226. arXiv: 1104.3913. DOI: 10.1145/2090236.2090255. ISBN 9781450311151. S2CID 13496699.
• Dwork, Cynthia; Feldman, Vitaly; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron (August 7, 2015). "The reusable holdout: Preserving validity in adaptive data analysis." Science. 349 (6248): 636–638. Bibcode: 2015Sci…349..636D. DOI: 10.1126/science.aaa9375. ISSN 0036-8075. PMID 26250683.