Toniann Pitassi

Toniann Pitassi, Oberwolfach 2017

Toniann Pitassi (* in Pittsburgh) ist eine kanadisch-US-amerikanische Informatikerin.

Pitassi studierte an der Pennsylvania State University mit dem Bachelor- und Master-Abschluss und wurde 1992 an der University of Toronto bei Stephen Cook promoviert (The Complexity of Weak Formal Systems). Als Post-Doktorandin war sie zwei Jahre an der University of California, San Diego. Danach war sie zwei Jahre Assistant Professor an der University of Pittsburgh und anschließend vier Jahre an der University of Arizona. Ab 2001 war sie Professorin an der University of Toronto (Bell Research Chair) und ab 2021 an der Columbia University (Jeffrey L. and Brenda Bleustein Professor of Engineering).

2017, 2019, 2020 und 2021 war sie als Gastprofessorin am Institute for Advanced Study (und 2004 Mitglied des IAS).

Pitassi befasst sich mit Komplexitätstheorie und insbesondere Beweis-Komplexität in verschiedenen formalen Systemen der Mathematik (Logik) und Informatik, aber auch zum Beispiel Kommunikationskomplexität und Schaltkreiskomplexität. Eine Motivation für ihre Forschung ist das P-NP-Problem, wozu sie als Vorstufe Beweiskomplexität in Logik-Systemen (und Erfüllbarkeitsproblemen) untersucht, mit dem zentralen Problem zu untersuchen, welche Tautologien effiziente Beweise in Standard-Beweissystemen besitzen. Dabei wird Effizienz in Zeit, Raum und Zufälligkeit gemessen. Unter anderem gab sie 1993 mit Paul Beame und Russell Impagliazzo exponentieller untere Grenzen für das Schubfachprinzip in Frege- bzw. Hilbert-Systemen (Standardsystemen der Beweistheorie). Mit Beame, Richard M. Karp und Michael Saks bewies sie exponentielle untere Schranken für die Komplexität von Resolutionsbeweisen für dicht verteilte zufällige 3-CNF und subexponentielle obere Schranken mit Hilfe des Davis-Putnam-Verfahrens.

Sie befasst sich auch mit Differential Privacy (die Privatsphäre erhaltene Datenverarbeitungsverfahren), nicht-diskriminierendes Maschinenlernen.

2012 erhielt sie den EATCS-Award. 2018 wurde sie Fellow der Association for Computing Machinery. 1998 war sie eingeladene Sprecherin auf dem Internationalen Mathematikerkongress in Berlin (Unsolvable systems of equations and proof theory). 2012 leitete sie das Programmkomitee für das ACM Symposium on Theory of Computing (STOC). 2022 wurde sie Mitglied der National Academy of Sciences.

Sie ist mit dem Informatikprofessor an der Columbia-University Richard Zemel verheiratet.

Schriften (Auswahl)

• mit Paul Beame, Russell Impagliazzo: Exponential lower bounds for the pigeonhole principle, Computational Complexity, Band 3, 1993, S. 97–140
• mit Paul Beame: Simplified and improved resolution lower bounds, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (STOC), 1996, S. 274–282
• mit Maria Bonet, Ran Raz: Lower bounds for cutting planes proofs with small coefficients, Journal of Symbolic Logic, Band 62, 1997, S. 708–728
• mit Paul Beame: Propositional proof complexity: past, present, and future, Bulletin of the European Association for Theoretical Computer Science, 1998, S. 66–89, nachgedruckt in: Current Trends in Theoretical Computer Science, World Scientific, 2001
• mit Paul Beame, Richard Karp, Michael Saks: On the complexity of unsatisfiability proofs for random k-CNF formulas, Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), 1998, S. 561–571
• mit Paul Beame, Richard Karp, Michael Saks: The efficiency of resolution and Davis-Putnam procedures, SIAM Journal on Computing, Band 31, 2002, s. 1048–1075
• mit Cynthia Dwork, Moni Naor, Guy N. Rothblum: Differential privacy under continual observation, Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC), 2010, S. 715–724
• mit Cynthia Dwork, Moritz Hardt, Omer Reingold, Richard Zemel: Fairness Through Awareness, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12. New York, 2012, S. 214–226.
• mit Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Omer Reingold, Aaron Roth: The reusable holdout: Preserving validity in adaptive data analysis, Science, Band 349, 2015, S. 636–638. PMID 26250683.

Weblinks

• Webseite an der Universität Toronto