Toniann Pitassi is a Canadian-American mathematician and computer scientist who studies computational complexity theory. She currently holds the Jeffrey L. and Brenda Bleustein Professorship in Engineering at Columbia University. Previously, she served as the Bell Research Chair at the University of Toronto.

Academic career

Pitassi was born in Pittsburgh. She received her bachelor's and master's degrees from Pennsylvania State University before going to the University of Toronto for her doctoral studies. She earned her PhD in 1992 from the University of Toronto, with Stephen Cook as her advisor. After working as a postdoctoral researcher at the University of California, San Diego, she held teaching positions at the University of Pittsburgh and the University of Arizona. She returned to the University of Toronto in 2001 and was a professor in the Department of Computer Science and the Department of Mathematics until 2021, when she joined the faculty of Columbia University.

She gave a speech at the International Congress of Mathematicians in Berlin in 1998. She was the program chair 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 focuses on proof complexity, which is a part of computational complexity theory. This area studies the maximum and minimum lengths of mathematical proofs for logical statements in different proof systems. The aim is to use these findings to learn how long it takes to find proofs and to compare how effective different proof systems are.

Her research has led to several important findings, such as very long proofs for certain problems. For example, she found that Frege proofs require extremely long lengths to solve the pigeonhole principle. She also showed that the cutting-plane method has very long proofs for problems related to the maximum clique. Additionally, she found that resolution proofs are very long for dense random 3-satisfiability problems. However, she also discovered that using the Davis-Putnam algorithm, these same problems can be solved with shorter, though still complex, proofs.

She has also written several review articles with other researchers about proof complexity, including general proof complexity, algebraic proof complexity, and semialgebraic proof complexity.

Recognition

In 2018, Pitassi was chosen as an ACM Fellow 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 selected to join 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, pp. 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, pp. 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. pp. 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. pp. 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.