Tonianna Pitassiego

Toniann Pitassi
Pitassi na warsztatach MFO Proof Complexity and Beyond , 2017
Narodowość	Stany Zjednoczone Kanada
Edukacja	Uniwersytet Stanowy Pensylwanii uniwersytet w Toronto
Współmałżonek	Ryszard Zemel
Kariera naukowa
Pola	Matematyka, informatyka
Instytucje	Uniwersytet w Pittsburghu Uniwersytet Arizony uniwersytet w Toronto Uniwersytet Columbia
Doradca doktorski	Stefana Cooka

Toniann Pitassi jest kanadyjsko-amerykańskim matematykiem i informatykiem specjalizującym się w teorii złożoności obliczeniowej . Obecnie jest Jeffreyem L. i Brendą Bleustein profesorem inżynierii na Uniwersytecie Columbia i była katedrą Bell Research na Uniwersytecie w Toronto .

Kariera akademicka

Pochodząca z Pittsburgha Pitassi uzyskała tytuł licencjata i magistra na Uniwersytecie Stanowym Pensylwanii, po czym przeniosła się na Uniwersytet w Toronto, gdzie podjęła studia doktoranckie; doktoryzowała się w 1992 roku w Toronto pod kierunkiem Stephena Cooka . Po studiach podoktoranckich na Uniwersytecie Kalifornijskim w San Diego i stanowiskach wydziałowych na Uniwersytecie w Pittsburghu i Uniwersytecie Arizony , wróciła do Toronto w 2001 roku i była profesorem na Wydziale Informatyki i University of Toronto Department of Mathematics do 2021 roku, kiedy to dołączyła do wydziału Columbia University .

Była zaproszonym prelegentem na Międzynarodowym Kongresie Matematyków w Berlinie w 1998 roku. Była przewodniczącą programową Sympozjum Teorii Informatyki w 2012 roku . Od września do grudnia 2017 była profesorem wizytującym w Institute for Advanced Study .

Badania

Badania Pitassiego w dużej mierze koncentrowały się na złożoności dowodu , gałęzi teorii złożoności obliczeniowej , która poszukuje górnych i dolnych granic długości matematycznych dowodów twierdzeń logicznych w różnych sformalizowanych systemach dowodowych. Celem tego badania jest wykorzystanie tych granic do zrozumienia zarówno złożoności czasowej procedur dowodowych, jak i względnych mocnych stron różnych systemów dowodowych.

Wkład badawczy, jaki wniosła w tej dziedzinie, obejmuje wykładnicze dolne granice dla dowodów Frege'a zasady przegródek , wykładnicze dolne granice dla metody płaszczyzny tnącej stosowanej do twierdzeń wyprowadzonych z problemu maksymalnej kliki , wykładnicze dolne granice dla dowodów rozdzielczości gęstej losowości 3 -spełnialności i podwykładnicze górne granice dla tych samych gęstych przypadków losowych przy użyciu algorytmu Davisa-Putnama . Wraz z Paulem Beame napisała również ankietę dotyczącą złożoności dowodu.

Uznanie

Pitassi został wybrany na członka ACM w 2018 roku za „wkład w badania i edukację w dziedzinie złożoności obliczeniowej i dowodowej”.

Pitassi była także laureatką nagrody EATCS (Europejskiego Stowarzyszenia Informatyki Teoretycznej) w 2021 roku za jej „fundamentalny i szeroko zakrojony wkład w złożoność obliczeniową”.

Została wybrana do Narodowej Akademii Nauk w 2022 roku.

Wybrane publikacje

•    Pitassi, Toniann; Promień, Paweł; Impagliazzo, Russell (1993), „Wykładnicze dolne granice zasady przegródki”, Computational Complexity , 3 (2): 97–140, doi : 10,1007 / BF01200117 , MR 1233662 , S2CID 1046674 .
•    Promień, Paweł; Pitassi, Toniann (1996), „Uproszczone i ulepszone dolne granice rozdzielczości”, Proceedings of the 37th Annual Symposium on Foundations of Computer Science , s. 274–282, doi : 10.1109/SFCS.1996.548486 , MR 1450625 , S2CID 14341656 .
•    Bonet, Maria ; Pitassi, Toniann; Raz, Ran (1997), „Dolne granice dowodów płaszczyzn cięcia z małymi współczynnikami”, Journal of Symbolic Logic , 62 (3): 708–728, doi : 10,2307/2275569 , JSTOR 2275569 , MR 1472120 .
•   Promień, Paweł; Pitassi, Toniann (1998), „Złożoność dowodu zdań: przeszłość, teraźniejszość i przyszłość”, Biuletyn Europejskiego Stowarzyszenia Informatyki Teoretycznej (65): 66–89, MR 1650939 . Przedrukowano w Current Trends in Theoretical Computer Science , World Scientific, 2001, MR 1886033 .
•     Belka, Paweł; Karp, Ryszard ; Pitassi, Toniann; Saks, Michael (1998), „O złożoności dowodów niespełnialności dla losowych formuł k-CNF”, Proceedings of the 30th ACM Symposium on Theory of Computing , s. 561–571, ​​CiteSeerX 10.1.1.39.213 , doi : 10.1145/ 276698.276870 , MR 1715604 , S2CID 10262912 .
•   Promień, Paweł; Karp, Ryszard ; Pitassi, Toniann; Saks, Michael (2002), „Efektywność rozdzielczości i procedury Davisa-Putnama”, SIAM Journal on Computing , 31 (4): 1048–1075, doi : 10.1137 / S0097539700369156 , MR 1919956 .
•    Dwork, Cynthia; Naor, Moni; Pitassi, Toniann; Rothblum, Guy N. (2010). „Prywatność różnicowa pod ciągłą obserwacją”. Materiały z czterdziestego drugiego sympozjum ACM na temat teorii informatyki : 715–724. doi : 10.1145/1806689.1806787 . ISBN 9781450300506 . S2CID 1522154 .
•    Dwork, Cynthia; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Zemel, Richard (2012). „Sprawiedliwość poprzez świadomość”. Materiały z III Konferencji Innowacje w Informatyce Teoretycznej . ITCS '12. Nowy Jork, NY, USA: ACM: 214–226. ar Xiv : 1104.3913 . doi : 10.1145/2090236.2090255 . ISBN 9781450311151 . S2CID 13496699 .
•    Dwork, Cynthia; Feldman, Witalij; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron (7 sierpnia 2015). „Wstrzymanie wielokrotnego użytku: zachowanie ważności w adaptacyjnej analizie danych” . nauka . 349 (6248): 636–638. Bibcode : 2015Sci...349..636D . doi : 10.1126/science.aaa9375 . ISSN 0036-8075 . PMID 26250683 .