Par Ian Gormely
12 août 2021
« Je ne connais personne qui mérite plus le prix EATCS que Toni Pitassi. Au-delà de ses contributions inestimables à l'informatique fondamentale, sa compassion et son humanité l'ont poussée à mettre ses compétences considérables au service d'une société plus équitable. » – Garth Gibson, président et chef de la direction de l'Institut Vector
Un objectif unique guide Toni Pitassi, membre associée de la faculté Vector, depuis plus de 30 ans sa carrière en informatique : résoudre le problème P contre NP, l’un des plus grands problèmes non résolus de cette discipline. « Je ne sais pas si je pourrai y arriver de mon vivant », concède-t-elle.
L'implication de ce problème est importante. Si P, l'ensemble des problèmes faciles, était égal à NP, l'ensemble des problèmes très difficiles, de nombreux problèmes apparemment difficiles seraient en réalité solubles. Cependant, la plupart des mathématiciens ne sont pas de cet avis. « On peut y consacrer des années sans vraiment progresser. Comment, par exemple, caractériser chaque algorithme efficace et l'éliminer ensuite ? »
Pitassi souligne toutefois que, dans leur quête d'un problème, les chercheurs en résolvent inévitablement d'autres. « Chacun y contribue sous un angle différent, avec des idées différentes », explique-t-elle. « Ce faisant, la communauté théorique a généré de nombreuses idées et fait de nombreuses découvertes qui mènent à d'autres avancées, parfois inattendues. »
Bien qu'inattendues, ces pistes de recherche n'ont pas été vaines. Elle a récemment été choisie comme lauréate 2021 du prix de l'Association européenne d'informatique théorique, qui récompense « une contribution importante et largement reconnue à l'informatique théorique tout au long d'une carrière scientifique exceptionnelle ».
L'une des contributions majeures de Pitassi, mise de l'avant par l'Association lors de sa remise de prix, est le théorème de relèvement, dont elle a été l'une des pionnières. L'Association souligne que ce théorème a profondément transformé notre compréhension des arbres de décision et de la complexité de la communication. « Ce théorème a permis de résoudre avec succès de nombreux problèmes ouverts », affirme Pitassi, « et a mené à une bien meilleure compréhension de la nature du calcul dans de nombreux modèles restreints ». Cependant, la résolution du problème P vs NP « nécessitera de nouvelles avancées ».
Interrogée sur le prix EATCS et d'autres distinctions similaires, Pitassi reste modeste. « Je suis fière de certaines de mes réalisations, mais beaucoup de gens méritent ce genre de récompenses », dit-elle. « Je suis contente que des gens aient pris le temps de m'écrire. Ça me donne vraiment l'impression d'appartenir à une belle communauté de personnes qui prennent sur leur temps. »
Cette communauté s'est forgée au fil d'une longue carrière qui a mené Pitassi à travers le continent. Américaine de naissance, elle a obtenu son doctorat à l'Université de Toronto en 1992 avant de faire un postdoctorat à l'UC San Diego. Elle a ensuite occupé son premier poste de professeure à l'Université de Pittsburgh, puis a saisi une opportunité à l'Université d'Arizona, avant de retourner à l'Université de Toronto où elle est professeure au Département d'informatique et occupe un poste de six ans à l'Institut d'études avancées. « Je n'aurais jamais pensé m'installer pour de bon au Canada », confie-t-elle. « Mais je me suis sentie tellement supportée ici. Quand j'ai appris qu'un poste se libérait à l'Université de Toronto, j'étais ravie. »
Au cours des dernières années, ses travaux l'ont amenée à explorer une autre voie : l'utilisation de la technologie pour bâtir une société plus équitable. Plus précisément, Pitassi met ses compétences exceptionnelles au service du développement de cadres et d'approches permettant d'identifier et d'atténuer les biais dans les algorithmes d'apprentissage automatique.
Une solution technique est préférable à des « victoires politiques », surtout lorsqu'il s'agit de problèmes tels que la répartition des richesses et l'accès équitable aux biens et services essentiels. Pitassi reconnaît que cet objectif, aussi simple soit-il, est ambitieux et que trouver une solution technique est tout aussi complexe qu'une solution relevant des politiques publiques. « Il est même difficile de formuler la question avec précision. Bien sûr, au vu du reste de sa carrière, ce sont les efforts et les enseignements tirés de son parcours qui, en fin de compte, compteront.
