Par Ian Gormely

12 août 2021

"Je ne peux imaginer quelqu'un qui mérite davantage le prix EATCS que Toni Pitassi. Au-delà de ses contributions incalculables à l'informatique fondamentale, la compassion et l'humanité de Toni l'ont poussée à mettre ses compétences considérables au service de la création d'une société plus équitable. - Garth Gibson, président-directeur général de l'Institut Vector

Un seul objectif primordial guide Toni Pitassi, membre affilié de la faculté Vector, depuis plus de 30 ans dans le domaine de l'informatique : résoudre P versus NP, l'un des principaux problèmes non résolus de l'informatique. "Je ne sais pas si cet objectif est réalisable de mon vivant", concède Toni Pitassi. 

L'implication du problème est importante. Si P, un ensemble de problèmes faciles, était égal à NP, un ensemble de problèmes très difficiles, de nombreux problèmes qui semblent difficiles seraient en fait résolus. Cependant, la plupart des mathématiciens ne croient pas que ce soit le cas. "Vous pouvez passer de nombreuses années sans vraiment arriver à quoi que ce soit. Par exemple, comment peut-on caractériser chaque algorithme efficace et l'exclure ?"

Cependant, Mme Pitassi fait remarquer qu'en s'attaquant à un problème, les chercheurs en résolvent inévitablement d'autres. "Nous abordons tous le problème sous des angles différents et avec des idées différentes", explique-t-elle. "Au cours de ce processus, la communauté des théoriciens a trouvé de nombreuses idées et découvertes qui ont conduit à d'autres percées, parfois inattendues.

Bien qu'imprévus, ces parcours de recherche n'ont pas été vains. Elle a récemment été choisie comme lauréate 2021 du prix de l'Association européenne pour l'informatique théorique, qui récompense "les contributions étendues et largement reconnues à l'informatique théorique au cours d'une carrière scientifique de toute une vie".

L'une des tangentes que l'Association a soulignées en décorant Mme Pitassi est le théorème de levage qu'elle a contribué à mettre au point, notant que ce théorème a complètement transformé la compréhension des arbres de décision et de la complexité de la communication. Le théorème "a permis de résoudre de nombreux problèmes ouverts", explique Mme Pitassi, et "a conduit à une bien meilleure compréhension de la nature de l'informatique dans de nombreux modèles restreints". Mais la résolution de P vs NP "nécessitera d'autres percées".

Interrogée sur le prix EATCS et d'autres prix similaires, Mme Pitassi se montre discrète. "Je suis fière de ce que j'ai fait, mais beaucoup de gens méritent ce genre de prix", dit-elle. "Je suis heureuse que les gens aient pris le temps de m'écrire. Cela me donne l'impression de faire partie d'une communauté sympathique de personnes qui prennent le temps de s'occuper de leur vie. 

Cette communauté s'est forgée au cours d'une longue carrière qui a vu Mme Pitassi zigzaguer à travers le continent. Américaine d'origine, elle a obtenu son doctorat à l'université de Toronto en 1992 avant d'effectuer un post-doc à l'université de San Diego. Elle a occupé son premier poste de professeur à l'université de Pittsburgh, puis à l'université d'Arizona, avant de revenir à l'université de Toronto, où elle est professeur au département d'informatique et où elle a été nommée pour six ans à l'Institute of Advanced Study. Elle a été nommée pour six ans à l'Institute for Advanced Study. "Je n'aurais jamais pensé que nous nous retrouverions au Canada pour de bon", dit-elle. Mais je me suis sentie tellement soutenue ici. Lorsqu'il s'est avéré que l'université de Toronto avait un poste à pourvoir, j'étais très enthousiaste."

Ces dernières années, son travail l'a conduite sur une autre voie : utiliser la technologie pour créer une société plus équitable. Plus précisément, Mme Pitassi met ses formidables à l'élaboration de cadres et d'approches permettant d'identifier et d'atténuer les préjugés dans les algorithmes d'apprentissage automatique.

Une solution technique au problème est préférable à des "victoires politiques", lorsqu'il s'agit de problèmes tels que la répartition des richesses et l'accès équitable aux biens et services essentiels. M. Pitassi admet qu'un objectif aussi simple est néanmoins ambitieux et qu'il est aussi difficile de trouver une solution technique qu'une solution basée sur les politiques publiques. "Il est même difficile de formuler la question de manière précise. Bien entendu, si l'on considère la suite de la carrière de M. Pitassi, ce sont les efforts et l'apprentissage en cours de route qui compteront en fin de compte.