Toniann Pitassi

Informático canadiense-estadounidense

Toniann Pitassi es un matemático e informático canadiense-estadounidense especializado en teoría de la complejidad computacional . Actualmente es profesora Jeffrey L. y Brenda Bleustein de ingeniería en la Universidad de Columbia y fue catedrática de investigación Bell en la Universidad de Toronto . ^{[1] [2]}

Carrera académica

Originaria 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 realizar sus estudios de doctorado; Obtuvo su doctorado en 1992 en Toronto bajo la supervisión de Stephen Cook . Después de estudios postdoctorales en la Universidad de California, San Diego y puestos docentes 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 Ciencias de la Computación de la Universidad de Toronto. Matemáticas 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 invitada en el Instituto de Estudios Avanzados . ^[8]

Investigación

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 la longitud 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 realizado en esta área incluyen límites inferiores exponenciales para las pruebas de Frege del principio de casillero , ^[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 densas aleatorias de 3 satisfacibilidad , ^[11] y límites superiores subexponenciales para las mismas instancias aleatorias densas utilizando el algoritmo de Davis-Putnam . ^[12] Con Paul Beame, también escribió un estudio sobre la complejidad de la prueba. ^[13]

Reconocimiento

Pitassi fue elegido miembro de ACM en 2018 por "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; Haze, Paul; Impagliazzo, Russell (1993), "Límites inferiores exponenciales para el principio del casillero", Complejidad computacional , 3 (2): 97–140, doi :10.1007/BF01200117, MR  1233662, S2CID  1046674.
• Haze, 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, 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.
• Haze, Paul; Pitassi, Toniann (1998), "Complejidad de la prueba proposicional: pasado, presente y futuro", Boletín de la Asociación Europea de Informática Teórica (65): 66–89, SEÑOR  1650939. Reimpreso en Tendencias actuales en informática teórica , World Scientific, 2001, MR 1886033.
• Haze, Paul; Karp, Richard ; Pitassi, Toniann; Saks, Michael (1998), "Sobre la complejidad de las pruebas de insatisfacibilidad para fórmulas aleatorias k-CNF", Actas del 30º Simposio ACM sobre Teoría de la Computación , págs. 561–571, ​​CiteSeerX  10.1.1.39.213 , doi :10.1145/ 276698.276870, SEÑOR  1715604, S2CID  10262912.
• Haze, 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 continua observación". Actas del cuadragésimo segundo simposio de la ACM sobre teoría de la informática . págs. 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 . ITC '12. Nueva York, NY, Estados Unidos: ACM. págs. 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 reserva reutilizable: preservar la validez en el análisis de datos adaptativos". Ciencia . 349 (6248): 636–638. Código Bib : 2015 Ciencia... 349..636D. doi : 10.1126/ciencia.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 Colombia . Consultado el 4 de mayo de 2022 .
3. "Tonian Pitassi". Universidad de Toronto . Consultado el 31 de diciembre de 2017 .
4. Toniann Pitassi en el Proyecto de genealogía de matemáticas
5. "Plenaria de la ICM y oradores invitados". Unión Matemática Internacional . Consultado el 31 de diciembre de 2017 .
6. 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.
7. "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 .
8. "Tonian 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. Becarios de ACM 2018 honrados por logros fundamentales que sustentan la era digital, Association for Computing Machinery , 5 de diciembre de 2018
15. Premio EATCS 2021 - Laudatio para Toniann (Toni) Pitassi, Asociación Europea de Informática Teórica, 4 de junio de 2021
16. "Elección NAS de 2022". nasonline.org . Consultado el 4 de mayo de 2022 .