The EATCS Award 2021 - Laudatio for Toniann (Toni) Pitassi

The EATCS Awards Committee consisting of Johan Håstad, Marta Kwiatkowska (chair) and Éva Tardos has selected  Toniann (Toni) Pitassi (University of Toronto) as the recipient of the EATCS Award 2021. The award will be presented at ICALP 2021, which will be an Online Virtual Conference from the 12th till the 16th of July 2021.

The EATCS annually honors a respected scientist from our community with this prestigious EATCS Distinguished Achievements Award, to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career (see for more information, including the list of previous recipients)

The EATCS Award committee selects Professor Toniann (Toni) Pitassi (University of Toronto) as the recipient of the 2021 EATCS Award for her fundamental and wide-ranging contributions to computational complexity, which includes proving long-standing open problems, introducing new fundamental models, developing novel techniques and establishing new connections between different areas. Her work is very broad and has relevance in computational learning and optimisation, verification and SAT-solving, circuit complexity and communication complexity, and their applications.

The first notable contribution by Toni Pitassi was to develop lifting theorems: a way to transfer lower bounds from the (much simpler) decision tree model for any function f, to a lower bound, the much harder communication complexity model, for a simply related (2-party) function f’. This has completely transformed our state of knowledge regarding two fundamental computational models, query algorithms (decision trees) and communication complexity, as well as their relationship and applicability to other areas of theoretical computer science. These powerful and flexible techniques resolved numerous open problems (e.g., the super quadratic gap between probabilistic and quantum communication complexity), many of which were central challenges for decades.

Toni Pitassi has also had a remarkable impact in proof complexity. She introduced the fundamental algebraic Nullstellensatz and Ideal proof systems, and the geometric Stabbing Planes system. She gave the first nontrivial lower bounds on such long-standing problems as weak pigeon-hole principle and models like constant-depth Frege proof systems. She has developed new proof techniques for virtually all proof systems, and new SAT algorithms. She found novel connections of proof complexity, computational learning theory, communication complexity, circuit complexity, LP hierarchies, graph theory and more.

In the past few years Toni Pitassi has turned her attention to the field of algorithmic fairness, whose social importance is rapidly growing, in particular providing novel concepts and solutions based on causal modelling.

Summarising, Toni Pitassi’s contributions have transformed the field of computational complexity and neighbouring areas of theoretical computer science, and will continue to have a lasting impact. Furthermore, she is an outstanding mentor, great teacher and a dedicated TCS community member.

The EATCS Award Committee 2021

Johan Håstad
Marta Kwiatkowska (chair)
Éva Tardos your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.