Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Toniann Pitassi
open-in-new
<h2 id="academic-career">Academic career</h2> <p>A native of <a href="/facts/Pittsburgh/42yPHyS0">Pittsburgh</a>, Pitassi earned bachelor's and master's degrees at <a href="/facts/Pennsylvania_State_University/WMQagtjM">Pennsylvania State University</a> before moving to the <a href="/facts/University_of_Toronto/FpGjQNm9">University of Toronto</a> for her doctoral studies; she earned her PhD in 1992 from Toronto under the supervision of <a href="/facts/Stephen_Cook/GdE35Sm1">Stephen Cook</a>. After postdoctoral studies at the <a href="/facts/University_of_California%2c_San_Diego/srMClpNv">University of California, San Diego</a> and faculty positions at the <a href="/facts/University_of_Pittsburgh/U3lxG2L1">University of Pittsburgh</a> and <a href="/facts/University_of_Arizona/ehesIpKx">University of Arizona</a>, she returned to Toronto in 2001, and was a professor in the University of Toronto Department of Computer Science and <a href="/facts/University_of_Toronto_Department_of_Mathematics/f7RyzGtv">University of Toronto Department of Mathematics</a> until 2021, when she joined the faculty of <a href="/facts/Columbia_University/Hlf1gw53">Columbia University</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p><p>She was an invited speaker at <a href="/facts/International_Congress_of_Mathematicians/qQX4kVpe">International Congress of Mathematicians</a> in Berlin in 1998.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> She was the program chair for the 2012 <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">Symposium on Theory of Computing</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> From September through December 2017, she was a visiting professor at the <a href="/facts/Institute_for_Advanced_Study/jQQCURKt">Institute for Advanced Study</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p> <h2 id="research">Research</h2> <p>Pitassi's research has largely focused on <a href="/facts/Proof_complexity/H4vEwkEW">proof complexity</a>, a branch of <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> that seeks <a href="/facts/Upper_and_lower_bounds/YJje9oC2">upper and lower bounds</a> on the lengths of <a href="/facts/Mathematical_proof/7ECDrU80">mathematical proofs</a> of <a href="/facts/Proposition/0877MFMD">logical propositions</a> within various formalized proof systems. The goal of this study is to use these bounds to understand both the <a href="/facts/Time_complexity/77T62gmf">time complexity</a> of proof-finding procedures, and the relative strengths of different proof systems. </p><p>Research contributions that she has made in this area include exponential lower bounds for <a href="/facts/Frege_system/L43r4Are">Frege proofs</a> of the <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a>,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> exponential lower bounds for the <a href="/facts/Cutting-plane_method/8V7TTfhx">cutting-plane method</a> applied to propositions derived from the <a href="/facts/Maximum_clique_problem/cVVBNP08">maximum clique problem</a>,<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> exponential lower bounds for <a href="/facts/Resolution_(logic)/16uDqkcD">resolution</a> proofs of dense random <a href="/facts/3-satisfiability/wBVRjWoy">3-satisfiability</a> instances,<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> and subexponential upper bounds for the same dense random instances using the <a href="/facts/Davis%25E2%2580%2593Putnam_algorithm/EowmALMU">Davis–Putnam algorithm</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> With various coauthors, she has several expositions and surveys: on proof complexity in general,<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> on algebraic proof complexity,<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> and on semialgebraic proof complexity.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <h2 id="recognition">Recognition</h2> <p>Pitassi was elected as an <a href="/facts/ACM_Fellow/kEuoGr62">ACM Fellow</a> in 2018 for "contributions to research and education in the fields of computational and proof complexity".<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> </p><p>Pitassi was also the recipient of the <a href="/facts/EATCS/4jlopeDl">EATCS</a> (European Association for Theoretical Computer Science) Award in 2021 for her "fundamental and wide-ranging contributions to computational complexity".<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p><p>She was named to the <a href="/facts/National_Academy_of_Sciences/M3oePVeG">National Academy of Sciences</a> in 2022.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a><a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> </p> <h2 id="selected-publications">Selected publications</h2> <ul><li>Pitassi, Toniann; Beame, Paul; <a href="/facts/Russell_Impagliazzo/GJ6W46dq">Impagliazzo, Russell</a> (1993), "Exponential lower bounds for the pigeonhole principle", <i>Computational Complexity</i>, 3 (2): 97–140, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01200117">10.1007/BF01200117</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1233662">1233662</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1046674">1046674</a>.</li> <li>Beame, Paul; Pitassi, Toniann (1996), "Simplified and improved resolution lower bounds", <a href="/facts/Symposium_on_Foundations_of_Computer_Science/t0BvR59t"><i>Proceedings of the 37th Annual Symposium on Foundations of Computer Science</i></a>, pp. 274–282, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.1996.548486">10.1109/SFCS.1996.548486</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-8186-7594-2, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1450625">1450625</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14341656">14341656</a>.</li> <li><a href="/facts/Mar%25C3%25ADa_Luisa_Bonet/HvVlGCQH">Bonet, Maria</a>; Pitassi, Toniann; <a href="/facts/Ran_Raz/0erygJsz">Raz, Ran</a> (1997), "Lower bounds for cutting planes proofs with small coefficients", <i><a href="/facts/Journal_of_Symbolic_Logic/lfXVXcoy">Journal of Symbolic Logic</a></i>, 62 (3): 708–728, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2275569">10.2307/2275569</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2275569">2275569</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1472120">1472120</a>.</li> <li>Beame, Paul; Pitassi, Toniann (1998), "Propositional proof complexity: past, present, and future", <i>Bulletin of the European Association for Theoretical Computer Science</i> (65): 66–89, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1650939">1650939</a>. Reprinted in <i>Current Trends in Theoretical Computer Science</i>, World Scientific, 2001, <a href="/facts/MR_(identifier)/uP137L11">MR</a><a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1886033">1886033</a>.</li> <li>Beame, Paul; <a href="/facts/Richard_M._Karp/XtYCL0nA">Karp, Richard</a>; Pitassi, Toniann; <a href="/facts/Michael_Saks_(mathematician)/DmMG4Cy1">Saks, Michael</a> (1998), "On the complexity of unsatisfiability proofs for random k-CNF formulas", <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG"><i>Proceedings of the 30th ACM Symposium on Theory of Computing</i></a>, pp. 561–571, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.213">10.1.1.39.213</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F276698.276870">10.1145/276698.276870</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-89791-962-9, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1715604">1715604</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:10262912">10262912</a>.</li> <li>Beame, Paul; <a href="/facts/Richard_M._Karp/XtYCL0nA">Karp, Richard</a>; Pitassi, Toniann; <a href="/facts/Michael_Saks_(mathematician)/DmMG4Cy1">Saks, Michael</a> (2002), "The efficiency of resolution and Davis-Putnam procedures", <i><a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a></i>, 31 (4): 1048–1075, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2FS0097539700369156">10.1137/S0097539700369156</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1919956">1919956</a>.</li> <li>Dwork, Cynthia; Naor, Moni; Pitassi, Toniann; Rothblum, Guy N. (2010). "Differential privacy under continual observation". <i>Proceedings of the forty-second ACM symposium on Theory of computing</i>. pp. 715–724. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1806689.1806787">10.1145/1806689.1806787</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450300506. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1522154">1522154</a>.</li> <li>Dwork, Cynthia; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Zemel, Richard (2012). "Fairness through awareness". <i>Proceedings of the 3rd Innovations in Theoretical Computer Science Conference</i>. ITCS '12. New York, NY, USA: ACM. pp. 214–226. <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1104.3913">1104.3913</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2090236.2090255">10.1145/2090236.2090255</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450311151. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:13496699">13496699</a>.</li> <li>Dwork, Cynthia; Feldman, Vitaly; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron (August 7, 2015). <a href="https://doi.org/10.1126%2Fscience.aaa9375">"The reusable holdout: Preserving validity in adaptive data analysis"</a>. <i>Science</i>. 349 (6248): 636–638. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2015Sci...349..636D">2015Sci...349..636D</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1126%2Fscience.aaa9375">10.1126/science.aaa9375</a>. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0036-8075">0036-8075</a>. <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/26250683">26250683</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"toniann pitassi | Department of Computer Science, Columbia University". www.cs.columbia.edu. Retrieved May 4, 2022. <a href="https://www.cs.columbia.edu/tag/toniann-pitassi/" target="_blank">https://www.cs.columbia.edu/tag/toniann-pitassi/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"Four Columbians Elected to the National Academy of Sciences". Columbia News. Retrieved May 4, 2022. <a href="https://news.columbia.edu/news/four-columbians-elected-national-academy-sciences" target="_blank">https://news.columbia.edu/news/four-columbians-elected-national-academy-sciences</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>"Toniann Pitassi". University of Toronto. Retrieved December 31, 2017. <a href="http://www.cs.toronto.edu/~toni/" target="_blank">http://www.cs.toronto.edu/~toni/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Toniann Pitassi at the Mathematics Genealogy Project <a href="https://mathgenealogy.org/id.php?id=80101" target="_blank">https://mathgenealogy.org/id.php?id=80101</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>"ICM Plenary and Invited Speakers". International Mathematical Union. Retrieved December 31, 2017. <a href="https://www.mathunion.org/icm-plenary-and-invited-speakers?combine=Pitassi" target="_blank">https://www.mathunion.org/icm-plenary-and-invited-speakers?combine=Pitassi</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Pitassi, Toniann (1998). "Unsolvable systems of equations and proof complexity". Doc. Math. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III. pp. 451–458. <a href="https://www.elibm.org/ft/10011601000" target="_blank">https://www.elibm.org/ft/10011601000</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>"STOC 2012 - 44th ACM Symposium on Theory of Computing". New York University, Computer Science Department. Retrieved December 31, 2017. <a href="https://cs.nyu.edu/~stoc2012/default.htm" target="_blank">https://cs.nyu.edu/~stoc2012/default.htm</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>"Toniann Pitassi". Institute for Advanced Study. Retrieved December 31, 2017. <a href="https://www.ias.edu/scholars/toniann-pitassi" target="_blank">https://www.ias.edu/scholars/toniann-pitassi</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Pitassi, Beame & Impagliazzo (1993). - 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 <a href="https://doi.org/10.1007%2FBF01200117" target="_blank">https://doi.org/10.1007%2FBF01200117</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Bonet, Pitassi & Raz (1997). - 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 <a href="https://doi.org/10.2307%2F2275569" target="_blank">https://doi.org/10.2307%2F2275569</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Beame & Pitassi (1996); Beame et al. (2002). - 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 <a href="https://doi.org/10.1109%2FSFCS.1996.548486" target="_blank">https://doi.org/10.1109%2FSFCS.1996.548486</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Beame et al. (1998); Beame et al. (2002). - 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 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.213" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.213</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Beame, Paul; Pitassi, Toniann (1998), "Propositional Proof Complexity: Past, Present and Future", Bulletin EATCS (65): 66–89 <a href="https://eccc.weizmann.ac.il/eccc-reports/1998/TR98-067/index.html" target="_blank">https://eccc.weizmann.ac.il/eccc-reports/1998/TR98-067/index.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Pitassi, Toniann; Tzameret, Iddo (2016), "Algebraic proof complexity: progress, frontiers and challenges", ACM SIGLOG News, 3 (3): 21–43, doi:10.1145/2984450.2984455 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Fleming, Noah; Kothari, Pravesh; Pitassi, Toniann (2019). "Semialgebraic Proofs and Efficient Algorithm Design". Foundations and Trends in Theoretical Computer Science. 14 (1–2). now Publishers: 1–221. doi:10.1561/0400000086. <a href="https://eccc.weizmann.ac.il/report/2019/106/" target="_blank">https://eccc.weizmann.ac.il/report/2019/106/</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>2018 ACM Fellows Honored for Pivotal Achievements that Underpin the Digital Age, Association for Computing Machinery, December 5, 2018 <a href="https://www.acm.org/media-center/2018/december/fellows-2018" target="_blank">https://www.acm.org/media-center/2018/december/fellows-2018</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>The EATCS Award 2021 - Laudatio for Toniann (Toni) Pitassi, European Association for Theoretical Computer Science, June 4, 2021 <a href="https://eatcs.org/index.php/component/content/article/1-news/2877-the-eatcs-award-2021-laudatio-for-toniann-toni-pitassi-" target="_blank">https://eatcs.org/index.php/component/content/article/1-news/2877-the-eatcs-award-2021-laudatio-for-toniann-toni-pitassi-</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>"Four Columbians Elected to the National Academy of Sciences". Columbia News. Retrieved May 4, 2022. <a href="https://news.columbia.edu/news/four-columbians-elected-national-academy-sciences" target="_blank">https://news.columbia.edu/news/four-columbians-elected-national-academy-sciences</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>"2022 NAS Election". nasonline.org. Retrieved May 4, 2022. <a href="http://www.nasonline.org/news-and-multimedia/news/2022-nas-election.html" target="_blank">http://www.nasonline.org/news-and-multimedia/news/2022-nas-election.html</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> </ol>