Toniann Pitassi es un matemático e informático canadiense y estadounidense que se especializa en la teoría de la complejidad computacional .
Toniann Pitassi | |
---|---|
Nacionalidad | Estadounidense, canadiense |
alma mater | Universidad de Toronto |
Esposos) | Richard Zemel |
Carrera científica | |
Campos | Matemáticas Informática |
Instituciones | Universidad de Toronto |
Asesor de doctorado | Stephen Cook |
Carrera académica
Un nativo de Pittsburgh , Pitassi obtuvo una licenciatura y una maestría en la Universidad Estatal de Pensilvania antes de trasladarse a la Universidad de Toronto para sus estudios de doctorado; obtuvo su Ph.D. en 1992 desde Toronto bajo la supervisión de Stephen Cook . Después de los estudios de postdoctorado en la Universidad de California, San Diego y posiciones de la facultad en la Universidad de Pittsburgh y la Universidad de Arizona , regresó a Toronto en 2001, y ahora es un profesor de la Universidad de Departamento de Ciencias de la Computación de Toronto y la Universidad de Departamento de Toronto de Matemáticas . [1] [2]
Fue oradora invitada en el Congreso Internacional de Matemáticos en Berlín en 1998. [3] [4] Fue la presidenta del programa del Simposio de Teoría de la Computación de 2012 . [5] Desde septiembre hasta diciembre de 2017, fue profesora visitante en el Instituto de Estudios Avanzados . [6]
Investigar
La investigación de Pitassi se ha centrado en gran medida en la complejidad de la prueba , una rama de la teoría de la complejidad computacional que busca límites superiores e inferiores en las longitudes de las pruebas matemáticas de proposiciones lógicas dentro de varios sistemas de prueba formalizados. El objetivo de este estudio es utilizar estos límites para comprender tanto la complejidad temporal de los procedimientos de búsqueda de pruebas como las fortalezas relativas de los diferentes sistemas de prueba.
Las contribuciones de investigación que ha hecho en esta área incluyen límites inferiores exponenciales para las pruebas de Frege del principio del casillero , [7] límites inferiores exponenciales para el método del plano de corte aplicado a proposiciones derivadas del problema de camarilla máxima , [8] límites inferiores exponenciales para pruebas de resolución de instancias aleatorias densas de 3-satisfacibilidad , [9] y límites superiores subexponenciales para las mismas instancias aleatorias densas utilizando el algoritmo Davis-Putnam . [10] Con Paul Beame, también escribió una encuesta sobre la complejidad de las pruebas. [11]
Reconocimiento
Pitassi fue elegido miembro de la ACM en 2018 por "contribuciones a la investigación y la educación en los campos de la complejidad computacional y de prueba". [12]
Pitassi también recibió el premio EATCS (Asociación Europea de Ciencias de la Computación Teórica) en 2021 por sus "contribuciones fundamentales y de amplio alcance a la complejidad computacional". [13]
Publicaciones Seleccionadas
- Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell (1993), "Límites inferiores exponenciales para el principio de casillero", Complejidad computacional , 3 (2): 97–140, doi : 10.1007 / BF01200117 , MR 1233662 , S2CID 1046674.
- Beame, Paul; Pitassi, Toniann (1996), "Límites inferiores de resolución simplificados y mejorados", Actas del 37º Simposio anual sobre los fundamentos de la informática , págs. 274-282, doi : 10.1109 / SFCS.1996.548486 , MR 1450625 , S2CID 14341656.
- Bonet, María; Pitassi, Toniann; Raz, Ran (1997), "Límites inferiores para pruebas de planos de corte con coeficientes pequeños", Journal of Symbolic Logic , 62 (3): 708–728, doi : 10.2307 / 2275569 , JSTOR 2275569 , MR 1472120.
- Beame, Paul; Pitassi, Toniann (1998), "Complejidad de la prueba proposicional: pasado, presente y futuro", Boletín de la Asociación Europea de Ciencias de la Computación Teórica (65): 66-89, MR 1650939. Reimpreso en Current Trends in Theoretical Computer Science , World Scientific, 2001, MR1886033 .
- Beame, Paul; Karp, Richard ; Pitassi, Toniann; Saks, Michael (1998), "Sobre la complejidad de las pruebas de insatisfacción para las fórmulas k-CNF aleatorias", Actas del 30º Simposio de ACM sobre Teoría de la Computación , págs. 561–571, CiteSeerX 10.1.1.39.213 , doi : 10.1145 / 276698.276870 , MR 1715604 , S2CID 10262912.
- Beame, Paul; Karp, Richard ; Pitassi, Toniann; Saks, Michael (2002), "La eficiencia de la resolución y los procedimientos de Davis-Putnam", SIAM Journal on Computing , 31 (4): 1048-1075, doi : 10.1137 / S0097539700369156 , MR 1919956.
- Dwork, Cynthia; Naor, Moni; Pitassi, Toniann; Rothblum, Guy N. (2010). "Privacidad diferencial bajo observación continua". Actas del cuadragésimo segundo simposio de ACM sobre teoría de la computación : 715–724. doi : 10.1145 / 1806689.1806787 . ISBN 9781450300506. S2CID 1522154 .
- Dwork, Cynthia; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Zemel, Richard (2012). "Equidad a través de la conciencia". Actas de la 3ª Conferencia sobre Innovaciones en Informática Teórica . ITCS '12. Nueva York, NY, EE. UU .: 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 de agosto de 2015). "La retención reutilizable: preservar la validez en el análisis de datos adaptativos" . Ciencia . 349 (6248): 636–638. Código bibliográfico : 2015Sci ... 349..636D . doi : 10.1126 / science.aaa9375 . ISSN 0036-8075 . PMID 26250683 .
Referencias
- ^ "Toniann Pitassi" . Universidad de Toronto . Consultado el 31 de diciembre de 2017 .
- ^ Toniann Pitassi en el Proyecto de genealogía matemática
- ^ "Plenario de la ICM y oradores invitados" . Unión Matemática Internacional . Consultado el 31 de diciembre de 2017 .
- ^ Pitassi, Toniann (1998). "Sistemas de ecuaciones irresolubles y complejidad de la prueba" . Doc. Matemáticas. (Bielefeld) Extra Vol. ICM Berlín, 1998, vol. III . págs. 451–458.
- ^ "STOC 2012 - 44º Simposio ACM sobre Teoría de la Computación" . Universidad de Nueva York , Departamento de Ciencias de la Computación . Consultado el 31 de diciembre de 2017 .
- ^ "Toniann Pitassi" . Instituto de Estudios Avanzados . Consultado el 31 de diciembre de 2017 .
- ^ Pitassi, Beame e Impagliazzo (1993) .
- ^ Bonet, Pitassi y Raz (1997) .
- ^ Beame y Pitassi (1996) ; Beame y col. (2002) .
- ^ Beame y col. (1998) ; Beame y col. (2002) .
- ^ Beame y Pitassi (1998) .
- ^ Los becarios de ACM 2018 reconocidos por los logros fundamentales que sustentan la era digital , Association for Computing Machinery , 5 de diciembre de 2018
- ^ The EATCS Award 2021 - Laudatio for Toniann (Toni) Pitassi , European Association for Theoretical Computer Science, 4 de junio de 2021