Toniann Pitassi

Toniann Pitassi is a Canadian and American mathematician and computer scientist specializing in computational complexity theory.

Toniann Pitassi
NationalityAmerican, Canadian
Alma materUniversity of Toronto
Spouse(s)Richard Zemel
Scientific career
FieldsMathematics
Computer Science
InstitutionsUniversity of Toronto
Doctoral advisorStephen Cook

Academic career

A native of Pittsburgh, Pitassi earned bachelor's and master's degrees at Pennsylvania State University before moving to the University of Toronto for her doctoral studies; she earned her Ph.D. in 1992 from Toronto under the supervision of Stephen Cook. After postdoctoral studies at the University of California, San Diego and faculty positions at the University of Pittsburgh and University of Arizona, she returned to Toronto in 2001, and is now a professor in the University of Toronto Department of Computer Science and University of Toronto Department of Mathematics.[1][2]

She was an invited speaker at International Congress of Mathematicians in Berlin in 1998.[3][4] She was the program chair for the 2012 Symposium on Theory of Computing.[5] From September through December 2017, she was a Visiting Professor at the Institute for Advanced Study.[6]

Research

Pitassi's research has largely focused on proof complexity, a branch of computational complexity theory that seeks upper and lower bounds on the lengths of mathematical proofs of logical propositions within various formalized proof systems. The goal of this study is to use these bounds to understand both the time complexity of proof-finding procedures, and the relative strengths of different proof systems.

Research contributions that she has made in this area include exponential lower bounds for Frege proofs of the pigeonhole principle,[7] exponential lower bounds for the cutting-plane method applied to propositions derived from the maximum clique problem,[8] exponential lower bounds for resolution proofs of dense random 3-satisfiability instances,[9] and subexponential upper bounds for the same dense random instances using the Davis–Putnam algorithm.[10] With Paul Beame, she also wrote a survey of proof complexity.[11]

Recognition

Pitassi was elected as an ACM Fellow in 2018 for "contributions to research and education in the fields of computational and proof complexity".[12]

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.
  • 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, MR 1450625.
  • 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, MR1886033.
  • 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, MR 1715604.
  • 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: 715–724. doi:10.1145/1806689.1806787. ISBN 9781450300506.
  • 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: 214–226. arXiv:1104.3913. doi:10.1145/2090236.2090255. ISBN 9781450311151.
  • Dwork, Cynthia; Feldman, Vitaly; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron (2015-08-07). "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.
gollark: Anyway, did you know that you'll either implode or not implode in the next femtosecond?
gollark: Hermaphrodite things exist and you can easily imagine aliens with more or fewer sexes.
gollark: Not all binary choices have even odds either way, and there are more than 2 anyway.
gollark: We don't have data on any, so I don't know what you're referring to there.
gollark: If you pick a random species on Earth the chance it has two sexes is not actually exactly 50%, see. Even if that was true, it would be ridiculous to just assume alien life would turn out exactly the same way.

References
  1. "Toniann Pitassi". University of Toronto. Retrieved 2017-12-31.
  2. Toniann Pitassi at the Mathematics Genealogy Project
  3. "ICM Plenary and Invited Speakers". International Mathematical Union. Retrieved 2017-12-31.
  4. Pitassi, Toniann (1998). "Unsolvable systems of equations and proof complexity". Doc. Math. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III. pp. 451–458.
  5. "STOC 2012 - 44th ACM Symposium on Theory of Computing". New York University, Computer Science Department. Retrieved 2017-12-31.
  6. "Toniann Pitassi". Institute for Advanced Study. Retrieved 2017-12-31.
  7. Pitassi, Beame & Impagliazzo (1993).
  8. Bonet, Pitassi & Raz (1997).
  9. Beame & Pitassi (1996); Beame et al. (2002).
  10. Beame et al. (1998); Beame et al. (2002).
  11. Beame & Pitassi (1998).
  12. 2018 ACM Fellows Honored for Pivotal Achievements that Underpin the Digital Age, Association for Computing Machinery, December 5, 2018
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.