Toniann Pitassi is a Canadian-American mathematician and computer scientist who specializes in computational complexity theory. She is currently the Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was previously the Bell Research Chair at the University of Toronto.

Academic career

Pitassi was born in Pittsburgh. She got her bachelor's and master's degrees at Pennsylvania State University before moving to the University of Toronto to study for her doctorate. She earned her PhD in 1992 from the University of Toronto under the supervision of Stephen Cook. After completing postdoctoral work at the University of California, San Diego, and teaching positions at the University of Pittsburgh and University of Arizona, she returned to Toronto in 2001. She was a professor in the University of Toronto Department of Computer Science and the University of Toronto Department of Mathematics until 2021, when she joined the faculty at 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 through December 2017, she was a visiting professor at the Institute for Advanced Study.

Research

Pitassi's research has mainly studied proof complexity, an area of computational complexity theory that tries to find limits on how long mathematical proofs can be for logical statements in different formal proof systems. The purpose of this research is to learn about how long it takes to find proofs and to compare how effective different proof systems are.

Her work includes showing that Frege proofs for the pigeonhole principle require a very large number of steps, proving that the cutting-plane method needs many steps for problems related to the maximum clique, and demonstrating that resolution proofs for complex 3-satisfiability problems also need many steps. She also found that the Davis–Putnam algorithm can solve these same problems in less time than exponential methods. With other researchers, she has written several articles explaining proof complexity, algebraic proof complexity, and semialgebraic proof complexity.

Recognition

In 2018, Pitassi was chosen as an ACM Fellow for her work in the areas of computational and proof complexity. In 2021, she received the EATCS Award for her important and broad contributions to computational complexity. In 2022, she was named 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, 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.