Toniann Pitassi

Científico informático canadiense-estadounidense

Toniann Pitassi es una matemática y científica informática canadiense-estadounidense especializada en teoría de la complejidad computacional . Actualmente es profesora de ingeniería Jeffrey L. y Brenda Bleustein en la Universidad de Columbia y fue titular de la Cátedra de Investigación Bell en la Universidad de Toronto . ^{[1] [2]}

Carrera académica

Originaria de Pittsburgh , Pitassi obtuvo su licenciatura y maestría en la Universidad Estatal de Pensilvania antes de trasladarse a la Universidad de Toronto para realizar sus estudios de doctorado; obtuvo su doctorado en 1992 en Toronto bajo la supervisión de Stephen Cook . Después de realizar estudios posdoctorales en la Universidad de California, San Diego y ocupar puestos de profesora en la Universidad de Pittsburgh y la Universidad de Arizona , regresó a Toronto en 2001 y fue profesora en el Departamento de Ciencias de la Computación de la Universidad de Toronto y en el Departamento de Matemáticas de la Universidad de Toronto hasta 2021, cuando se incorporó a la facultad de la Universidad de Columbia . ^{[3] [4]}

Fue oradora invitada en el Congreso Internacional de Matemáticos en Berlín en 1998. ^{[5] [6]} Fue la presidenta del programa del Simposio sobre Teoría de la Computación de 2012. ^[7] De septiembre a diciembre de 2017 , fue profesora visitante en el Instituto de Estudios Avanzados . ^[8]

Investigación

La investigación de Pitassi se ha centrado principalmente en la complejidad de las pruebas , una rama de la teoría de la complejidad computacional que busca límites superiores e inferiores para las longitudes de las pruebas matemáticas de proposiciones lógicas dentro de varios sistemas de pruebas 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 pruebas.

Las contribuciones de investigación que ha hecho en esta área incluyen límites inferiores exponenciales para pruebas de Frege del principio del palomar , ^[9] límites inferiores exponenciales para el método del plano de corte aplicado a proposiciones derivadas del problema de camarilla máxima , ^[10] límites inferiores exponenciales para pruebas de resolución de instancias aleatorias densas de 3-satisfacibilidad , ^[11] y límites superiores subexponenciales para las mismas instancias aleatorias densas usando el algoritmo de Davis-Putnam . ^[12] Con Paul Beame, también escribió un estudio de la complejidad de las pruebas. ^[13]

Reconocimiento

Pitassi fue elegido miembro de la ACM en 2018 por sus "contribuciones a la investigación y la educación en los campos de la complejidad computacional y de prueba". ^[14]

Pitassi también recibió el premio EATCS (Asociación Europea de Informática Teórica) en 2021 por sus "contribuciones fundamentales y de amplio alcance a la complejidad computacional". ^[15]

Fue nombrada miembro de la Academia Nacional de Ciencias en 2022. ^{[2] [16]}

Publicaciones seleccionadas

• Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell (1993), "Límites inferiores exponenciales para el principio de palomar", Computational Complexity , 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 fundamentos de la informática , págs. 274-282, doi :10.1109/SFCS.1996.548486, MR  1450625, S2CID  14341656.
• Bonet, Maria ; 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 pruebas proposicionales: pasado, presente y futuro", Boletín de la Asociación Europea de Ciencias Informáticas Teóricas (65): 66–89, MR  1650939. Reimpreso en Tendencias actuales en ciencias de la computación teórica , World Scientific, 2001, MR 1886033.
• Beame, Paul; Karp, Richard ; Pitassi, Toniann; Saks, Michael (1998), "Sobre la complejidad de las pruebas de insatisfacción para fórmulas aleatorias de k-CNF", Actas del 30.º Simposio de la 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 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 la ACM sobre teoría de la computación . págs. 715–724. doi :10.1145/1806689.1806787. ISBN 9781450300506.S2CID1522154  .​
• 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. pp. 214–226. arXiv : 1104.3913 . doi :10.1145/2090236.2090255. ISBN . 9781450311151. Número de identificación del S2C:  13496699.
• Dwork, Cynthia; Feldman, Vitaly; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron (7 de agosto de 2015). "El remanente reutilizable: preservación de la validez en el análisis de datos adaptativo". Science . 349 (6248): 636–638. Bibcode :2015Sci...349..636D. doi : 10.1126/science.aaa9375 . ISSN  0036-8075. PMID  26250683.

Referencias

1. "toniann pitassi | Departamento de Ciencias de la Computación, Universidad de Columbia". www.cs.columbia.edu . Consultado el 4 de mayo de 2022 .
2. "Cuatro colombianos elegidos para la Academia Nacional de Ciencias". Noticias de Columbia . Consultado el 4 de mayo de 2022 .
3. "Toniann Pitassi". Universidad de Toronto . Consultado el 31 de diciembre de 2017 .
4. Toniann Pitassi en el Proyecto de Genealogía Matemática
5. "Conferencistas invitados y plenarios del ICM". Unión Matemática Internacional . Consultado el 31 de diciembre de 2017 .
6. Pitassi, Toniann (1998). "Sistemas de ecuaciones irresolubles y complejidad de demostración". Doc. Math. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III . págs. 451–458.
7. "STOC 2012 - 44th ACM Symposium on Theory of Computing". Universidad de Nueva York , Departamento de Ciencias de la Computación . Consultado el 31 de diciembre de 2017 .
8. "Toniann Pitassi". Instituto de Estudios Avanzados . Consultado el 31 de diciembre de 2017 .
9. Pitassi, Beame e Impagliazzo (1993).
10. Bonet, Pitassi y Raz (1997).
11. Beame y Pitassi (1996); Beame et al. (2002).
12. Beame y col. (1998); Beame et al. (2002).
13. Beame y Pitassi (1998).
14. Los miembros de la ACM 2018 fueron reconocidos por sus logros fundamentales que sustentan la era digital, Association for Computing Machinery , 5 de diciembre de 2018
15. Premio EATCS 2021: elogio para Toniann (Toni) Pitassi, Asociación Europea de Informática Teórica, 4 de junio de 2021
16. "Elecciones NAS 2022". nasonline.org . Consultado el 4 de mayo de 2022 .