Toniann Pitassi

Toniann Pitassi
Pitassi på MFO -workshopen Proof Complexity and Beyond 2017
Nationalitet	Förenta staterna Kanada
Utbildning	Pennsylvania State University University of Toronto
Make	Richard Zemel
Vetenskaplig karriär
Fält	Matematik, datavetenskap
institutioner	University of Pittsburgh University of Arizona University of Toronto Columbia University
Doktorand rådgivare	Stephen Cook

Toniann Pitassi är en kanadensisk-amerikansk matematiker och datavetare specialiserad på beräkningskomplexitetsteori . Hon är för närvarande Jeffrey L. och Brenda Bleustein professor i teknik vid Columbia University och var Bell Research Chair vid University of Toronto .

Akademisk karriär

, född i Pittsburgh , tog kandidat- och magisterexamen vid Pennsylvania State University innan hon flyttade till University of Toronto för sina doktorandstudier; hon tog sin doktorsexamen 1992 från Toronto under ledning av Stephen Cook . Efter postdoktorala studier vid University of California, San Diego och fakultetsbefattningar vid University of Pittsburgh och University of Arizona , återvände hon till Toronto 2001 och var professor vid University of Toronto Department of Computer Science och University of Toronto Department of Matematik fram till 2021, då hon började på fakulteten vid Columbia University .

Hon var en inbjuden talare vid International Congress of Mathematicians i Berlin 1998. Hon var programordförande för 2012 års symposium on theory of computing . Från september till december 2017 var hon gästprofessor vid Institutet för avancerade studier .

Forskning

Pitassis forskning har till stor del fokuserat på beviskomplexitet , en gren av beräkningskomplexitetsteorin som söker övre och nedre gränser för längden på matematiska bevis för logiska påståenden inom olika formaliserade bevissystem. Målet med den här studien är att använda dessa gränser för att förstå både tidskomplexiteten för korrektursökningsprocedurer och de relativa styrkorna hos olika bevissystem.

Forskningsbidrag som hon har gjort inom detta område inkluderar exponentiella nedre gränser för Frege-bevis för duvhålsprincipen , exponentiella nedre gränser för skärplansmetoden tillämpad på propositioner härledda från maximiklickproblemet , exponentiella nedre gränser för upplösningsbevis av tät slumpmässig 3 -tillfredsställbarhetsinstanser och subexponentiella övre gränser för samma täta slumpmässiga instanser med Davis–Putnam-algoritmen . Med Paul Beame skrev hon också en undersökning om beviskomplexitet.

Erkännande

Pitassi valdes till ACM Fellow 2018 för "bidrag till forskning och utbildning inom områdena beräknings- och beviskomplexitet".

Pitassi var också mottagare av EATCS (European Association for Theoretical Computer Science) Award 2021 för hennes "grundläggande och omfattande bidrag till beräkningskomplexitet".

Hon utnämndes till National Academy of Sciences 2022.

Utvalda publikationer

•    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 4 1046677 .
• Beame, Paul; Pitassi, Toniann (1996), "Simplified and improved resolution lower bounds", Proceedings of the 37th Annual Symposium on Foundations of Computer Science ,    . 274–282, doi : 10.1109/SFCS.1996.548486 , MR 548486 , MR 5214, 6214 , 6214 , 5014 , 6214 s
•    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 . Omtryckt i 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 , s. 561–571, ​​CiteSeerX 10.1.1.39.213 , doi : 510/1110 276698.276870 , 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). "Differentiell integritet under ständig observation". Proceedings of the Forty-Second ACM Symposium on Theory of Computing : 715–724. doi : 10.1145/1806689.1806787 . ISBN 9781450300506 . S2CID 1522154 .
•    Dwork, Cynthia; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Zemel, Richard (2012). "Rättvisa genom medvetenhet". 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 . S2CID 13496699 .
•    Dwork, Cynthia; Feldman, Vitaly; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron (7 augusti 2015). "The reusable holdout: Preserving validity in adaptive data analysis" . Vetenskap . 349 (6248): 636–638. Bibcode : 2015Sci...349..636D . doi : 10.1126/science.aaa9375 . ISSN 0036-8075 . PMID 26250683 .