Toniann Pitassi

Quality 0.50 · 0 views · Updated 2 months ago

Canadian-American computer scientist

title: "Toniann Pitassi" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["living-people", "21st-century-canadian-women-mathematicians", "canadian-women-computer-scientists", "university-of-toronto-alumni", "pennsylvania-state-university-faculty", "university-of-pittsburgh-faculty", "university-of-arizona-faculty", "academic-staff-of-the-university-of-toronto", "american-theoretical-computer-scientists", "canadian-theoretical-computer-scientists", "fellows-of-the-association-for-computing-machinery", "year-of-birth-missing-(living-people)", "columbia-university-faculty"] description: "Canadian-American computer scientist" topic_path: "technology/computing" source: "https://en.wikipedia.org/wiki/Toniann_Pitassi" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Canadian-American computer scientist ::

::data[format=table title="Infobox scientist"]

FieldValue
nameToniann Pitassi
imagePitassi2017 MFO21907.jpg
captionPitassi at the MFO workshop Proof Complexity and Beyond, 2017
nationality{{Flatlist
fieldsMathematics, computer science
workplaces{{Plainlist
education{{Plainlist
doctoral_advisorStephen Cook
signature
spouseRichard Zemel
::

| name = Toniann Pitassi | image = Pitassi2017 MFO21907.jpg | image_size = | caption = Pitassi at the MFO workshop Proof Complexity and Beyond, 2017 | birth_date = | birth_place = | death_date = | death_place = | citizenship = | nationality = {{Flatlist|

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

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 PhD 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 was a professor in the University of Toronto Department of Computer Science and University of Toronto Department of Mathematics until 2021, when she joined the faculty of Columbia University.

She was an invited speaker at 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 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, exponential lower bounds for the cutting-plane method applied to propositions derived from the maximum clique problem, exponential lower bounds for resolution proofs of dense random 3-satisfiability instances, and subexponential upper bounds for the same dense random instances using the Davis–Putnam algorithm. With various coauthors, she has several expositions and surveys: on proof complexity in general, on algebraic proof complexity, and on semialgebraic proof complexity.

Recognition

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

Pitassi was also the recipient of the EATCS (European Association for Theoretical Computer Science) Award in 2021 for her "fundamental and wide-ranging contributions to computational complexity".

She was named to the National Academy of Sciences in 2022.

Selected publications

  • {{citation | last1 = Pitassi | first1 = Toniann | last2 = Beame | first2 = Paul | last3 = Impagliazzo | first3 = Russell | author3-link = Russell Impagliazzo | doi = 10.1007/BF01200117 | issue = 2 | journal = Computational Complexity | mr = 1233662 | pages = 97–140 | title = Exponential lower bounds for the pigeonhole principle | volume = 3 | year = 1993| s2cid = 1046674
  • {{citation | last1 = Beame | first1 = Paul | last2 = Pitassi | first2 = Toniann | contribution = Simplified and improved resolution lower bounds | doi = 10.1109/SFCS.1996.548486 | mr = 1450625 | pages = 274–282 | title = Proceedings of the 37th Annual Symposium on Foundations of Computer Science | year = 1996| title-link = Symposium on Foundations of Computer Science | isbn = 0-8186-7594-2 | s2cid = 14341656
  • {{citation | last1 = Bonet | first1 = Maria | author1-link = María Luisa Bonet | last2 = Pitassi | first2 = Toniann | last3 = Raz | first3 = Ran | author3-link = Ran Raz | doi = 10.2307/2275569 | issue = 3 | journal = Journal of Symbolic Logic | mr = 1472120 | pages = 708–728 | title = Lower bounds for cutting planes proofs with small coefficients | volume = 62 | year = 1997| jstor = 2275569
  • {{citation | last1 = Beame | first1 = Paul | last2 = Pitassi | first2 = Toniann | issue = 65 | journal = Bulletin of the European Association for Theoretical Computer Science | mr = 1650939 | pages = 66–89 | title = Propositional proof complexity: past, present, and future | year = 1998}}. Reprinted in Current Trends in Theoretical Computer Science, World Scientific, 2001, .
  • {{citation | last1 = Beame | first1 = Paul | last2 = Karp | first2 = Richard | author2-link = Richard M. Karp | last3 = Pitassi | first3 = Toniann | last4 = Saks | first4 = Michael | author4-link = Michael Saks (mathematician) | contribution = On the complexity of unsatisfiability proofs for random k-CNF formulas | doi = 10.1145/276698.276870 | mr = 1715604 | pages = 561–571 | title = Proceedings of the 30th ACM Symposium on Theory of Computing | year = 1998| title-link = Symposium on Theory of Computing | isbn = 0-89791-962-9 | citeseerx = 10.1.1.39.213 | s2cid = 10262912
  • {{citation | last1 = Beame | first1 = Paul | last2 = Karp | first2 = Richard | author2-link = Richard M. Karp | last3 = Pitassi | first3 = Toniann | last4 = Saks | first4 = Michael | author4-link = Michael Saks (mathematician) | doi = 10.1137/S0097539700369156 | issue = 4 | journal = SIAM Journal on Computing | mr = 1919956 | pages = 1048–1075 | title = The efficiency of resolution and Davis-Putnam procedures | volume = 31 | year = 2002}}.

References

References

  1. "toniann pitassi {{!}} Department of Computer Science, Columbia University".
  2. "Four Columbians Elected to the National Academy of Sciences".
  3. "Toniann Pitassi".
  4. {{MathGenealogy
  5. "ICM Plenary and Invited Speakers".
  6. Pitassi, Toniann. (1998). "Doc. Math. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III".
  7. "STOC 2012 - 44th ACM Symposium on Theory of Computing".
  8. "Toniann Pitassi". Institute for Advanced Study.
  9. {{harvtxt. Pitassi. Beame. Impagliazzo. 1993.
  10. {{harvtxt. Bonet. Pitassi. Raz. 1997.
  11. {{harvtxt. Beame. Pitassi. 1996; {{harvtxt. Beame. Karp. Pitassi. Saks. 2002.
  12. {{harvtxt. Beame. Karp. Pitassi. Saks. 1998; {{harvtxt. Beame. Karp. Pitassi. Saks. 2002.
  13. (1998). "Propositional Proof Complexity: Past, Present and Future". Bulletin EATCS.
  14. (2016). "Algebraic proof complexity: progress, frontiers and challenges". ACM SIGLOG News.
  15. (2019). "Semialgebraic Proofs and Efficient Algorithm Design". now Publishers.
  16. (December 5, 2018). "2018 ACM Fellows Honored for Pivotal Achievements that Underpin the Digital Age". [[Association for Computing Machinery]].
  17. (June 4, 2021). "The EATCS Award 2021 - Laudatio for Toniann (Toni) Pitassi". European Association for Theoretical Computer Science.
  18. "2022 NAS Election".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

living-people21st-century-canadian-women-mathematicianscanadian-women-computer-scientistsuniversity-of-toronto-alumnipennsylvania-state-university-facultyuniversity-of-pittsburgh-facultyuniversity-of-arizona-facultyacademic-staff-of-the-university-of-torontoamerican-theoretical-computer-scientistscanadian-theoretical-computer-scientistsfellows-of-the-association-for-computing-machineryyear-of-birth-missing-(living-people)columbia-university-faculty