The European Association for Theoretical Computer Science has recognized Professor Toni Pitassi of the Department of Computer Science in the Faculty of Arts & Science with the 2021 EATCS Distinguished Achievements Award.
The annual award honours a scientist who has made “extensive and wide-ranging contributions” to theoretical computer science over the course of their career.
Pitassi, who is also appointed to the Department of Mathematics, has been recognized “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.”
The award citation highlights two notable contributions that she has made to the field:
Pitassi developed lifting theorems, cited as "powerful and flexible techniques” that resolved many open problems in theoretical computer science and “completely transformed our state of knowledge regarding two fundamental computational models, query algorithms (decision trees) and communication complexity.”
She was also recognized for the impact she has had in proof complexity. Pitassi introduced novel proof systems, developed new techniques for “virtually all proof systems,” and "found novel connections of proof complexity, computational learning theory, communication complexity, circuit complexity, LP hierarchies, graph theory and more.”
In summary, the award committee wrote: “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.”