Pasin Manurangsi : Prouver ce que les ordinateurs ne peuvent pas faire

En juillet 2011, la ville balnéaire thaïlandaise de Pattaya a accueilli la 23e Olympiade internationale d'informatique, la première fois que la Thaïlande organisait l'événement, et le Premier ministre Abhisit Vejjajiva a ouvert les jeux dans l'un de ses derniers actes officiels. Parmi l'équipe locale se trouvait un élève du Bangkok Christian College qui a terminé 14e sur 303 concurrents avec 524 points et a remporté une deuxième médaille d'or consécutive. Il a déclaré aux journalistes qu'il était satisfait de sa 14e place, que 524 points étaient plus que ce à quoi il s'attendait, et qu'il espérait que l'organisation de l'olympiade susciterait davantage d'intérêt pour l'informatique chez les jeunes thaïlandais. Quinze ans plus tard, Pasin Manurangsi est l'un des chercheurs dont le travail consiste à dire au reste de l'informatique quels problèmes sont sans espoir.

L'arc de l'Olympiade

Le parcours compétitif de Manurangsi se lit comme une expérience contrôlée d'amélioration. Lors de l'IOI 2009 en Bulgarie, il a marqué 516 points et a terminé 67e sur 301, remportant l'argent. En 2010, au Canada, il a marqué 704 points et a terminé 12e sur 297, remportant l'or. En 2011, sur son sol natal, il a de nouveau remporté l'or alors que la Thaïlande gagnait la médaille d'or par équipe lors de la compétition qu'elle accueillait pour la première fois. Trois participations, deux médailles d'or et une d'argent, et un bond de cinquante-cinq places dans le classement mondial entre sa première et sa deuxième tentative : la trajectoire de quelqu'un qui a traité une défaite comme un document de spécification plutôt que comme un verdict.

Le MIT et le problème de s'en approcher assez

Manurangsi a obtenu sa licence et son master au Massachusetts Institute of Technology (MIT), où ses travaux de master, supervisés par Dana Moshkovitz, concernaient des algorithmes d'approximation pour les jeux de projection. Ce choix de sujet a donné la direction de tout ce qui a suivi. L'approximation est le compromis pragmatique de la discipline : lorsqu'un problème ne peut pas être résolu exactement dans un temps raisonnable, on se contente d'une réponse garantie à l'intérieur d'un certain facteur de la meilleure. La question intéressante, et celle à laquelle Manurangsi est revenu sans cesse, est de savoir à quel point cette garantie peut être bonne avant de se heurter à un mur mathématique.

Berkeley : Le pays entre P et NP

Il a terminé son doctorat à l'Université de Californie à Berkeley en mai 2019, sous la co-supervision de Luca Trevisan et Prasad Raghavendra, avec Nikhil Srivastava dans le comité. La thèse s'intitulait Approximation and Hardness: Beyond P and NP (Approximation et dureté : au-delà de P et NP), et son ambition est visible dans le titre. La théorie de la complexité classique classe les problèmes dans ceux qui sont traitables (P) et ceux qui sont notoirement difficiles (NP-complets). La thèse de Manurangsi a délibérément cherché sur le terrain que ces catégories ne couvrent pas : des problèmes qui ne sont ni dans P ni connus pour être NP-difficiles, des problèmes paramétrés tels que l'ensemble k-dominant, k-clique, k-biclique, le réseau Steiner dirigé et les problèmes de réseaux, et — le plus contre-intuitif — des problèmes qui se situent confortablement dans P, comme la paire la plus proche et le produit intérieur maximum, mais qui résistent de toute façon à une approximation rapide. Le résumé affirme que le travail résout deux questions ouvertes de longue date dans la complexité paramétrée et livre les meilleurs facteurs d'inapproximabilité connus pour plusieurs problèmes. C'est une thèse sur le traçage de frontières, pas sur leur franchissement.

Le mur du k-sous-graphe le plus dense

Le seul résultat qui a fait sa renommée concerne le k-sous-graphe le plus dense : étant donné un réseau, trouver les k nœuds les plus étroitement liés. Manurangsi a prouvé que, sous l'hypothèse du temps exponentiel, aucun algorithme à temps polynomial ne peut obtenir un ratio d'approximation meilleur que n à la puissance 1/(log log n) élevé à une constante — et que sous l'hypothèse plus forte Gap-ETH, la barrière se resserre à n^f(n) pour toute fonction f tendant vers zéro, ce qui est très proche d'une dureté polynomiale. Crucialement, la construction a ce que le domaine appelle une complétude parfaite : elle distingue les graphes qui contiennent réellement une k-clique des graphes où chaque k-sous-graphe est clairsemé. L'article a remporté le prix Danny Lewin du meilleur article étudiant lors de STOC 2017, la conférence phare de la discipline en théorie.

Google, vie privée et division équitable

Depuis juillet 2019, Manurangsi est chercheur scientifique chez Google Research, où ses domaines répertoriés sont les algorithmes et la théorie, l'intelligence machine et l'anti-abus, et où il a accumulé plus d'une centaine de publications. Le centre de gravité s'est déplacé de l'inapproximabilité pure vers la confidentialité différentielle, la théorie de l'apprentissage et le choix social computationnel — division équitable, partage de consensus, agrégation de rangs privés, génération de données synthétiques. Un résultat récent montre que le partage de consensus jusqu'à O(√(n log n)) biens existe toujours pour n agents avec des utilités monotones, améliorant une borne précédente. Les récompenses ont continué d'arriver : meilleur article à WAOA 2021, meilleur article étudiant à ALT 2021, un meilleur article et une mention honorable de meilleur article à FORC 2026, plus une reconnaissance distinguée du comité de programme à IJCAI en 2021 et 2023 et le statut de meilleur relecteur à NeurIPS 2023.

Le voyage de retour

Depuis 2022, il fait partie des équipes d'encadrement pour l'Olympiade d'informatique de Thaïlande et ses camps d'olympiades mathématiques, et il a été membre invité de la délégation pour la Thaïlande à l'IOI 2024. Depuis 2023, il est également professeur adjoint à l'Université CMKL, enseignant les algorithmes, les structures de données et les algorithmes préservant la confidentialité. Le pipeline qui l'a produit est celui qu'il aide maintenant à gérer.

Pourquoi Pasin est appelé un génie

La qualité cognitive en jeu ici est inhabituellement spécifique, et ce n'est pas la vitesse brute. Le succès aux Olympiades récompense une résolution rapide et précise des problèmes sous la pression du temps ; la dureté de l'approximation récompense presque l'opposé — la patience de construire une réduction élaborée prouvant qu'une classe entière d'algorithmes est condamnée. Manurangsi est rare en ayant fait les deux à un niveau élevé, et la thèse de Berkeley en est la preuve : elle délimite un territoire que la plupart des chercheurs évitent précisément parce que les résultats négatifs sont plus difficiles à publier et plus difficiles à obtenir correctement. Un seul glissement logique dans une réduction invalide tout.

Le contre-argument honnête est substantiel. Rien dans le dossier sourcé — sa propre page d'accueil, son profil Google Research, sa thèse ou la couverture médiatique thaïlandaise contemporaine — n'utilise le mot « génie » à son sujet. Ses honneurs sont des prix décernés par des pairs des comités de conférence, qui reconnaissent le meilleur article dans une salle, pas un esprit pour les âges. L'informatique théorique est également implacablement collaborative ; ses plus de cent articles sont le produit d'une co-écriture, de séminaires et d'un groupe de Berkeley dirigé par deux des théoriciens de la complexité les plus forts du domaine. Son record aux IOI, bien qu'excellent, inclut une 67e place. Ce qui peut être dit sans inflation est plus étroit et plus intéressant : c'est un professionnel de premier ordre dans l'un des coins les plus techniquement exigeants des mathématiques, et son résultat déterminant a clôturé une question qui était restée ouverte pendant des années. Ce n'est pas la même chose qu'un génie, et il n'a jamais prétendu que c'était le cas.

Perspective

La carrière de Manurangsi a une forme inhabituelle pour un théoricien : les preuves d'impossibilité sont venues en premier, le travail de confidentialité appliquée en second. Le passage à la confidentialité différentielle et à la division équitable suggère quelqu'un qui, ayant établi où se trouvent les murs, préférerait maintenant construire à l'intérieur. L'encadrement des olympiades thaïlandaises pourrait s'avérer être l'héritage le plus durable — un pays qui a accueilli l'IOI une fois, et qui fait maintenant grandir les personnes qui la gagnent.