KHOT SUBHASH (1978- )

Le mathématicien indien Subhash Khot est un théoricien de l’informatique, spécialiste des problèmes d’optimisation dans ce qu’il est convenu d’appeler la théorie de la complexité. Né le 10 juin 1978 à Ichalkaranji, ville moyenne de l’État du Maharashtra dans l’ouest de l’Inde, Khot est le fils de deux médecins. Classé premier au concours d’entrée de l’Institut indien de technologie (I.T.T.) de Bombay en 1995, il y obtient sa licence en informatique en 1999 et s’installe aux États-Unis pour ses études de doctorat qu’il accomplit sous la direction du professeur Sanjeev Arora (né en 1968) à l’université de Princeton. Son travail sur « des techniques nouvelles appliquées à la vérification statistique de preuves et de résultats d’inapproximation » est immédiatement reconnu comme extrêmement novateur. Après sa thèse soutenue en 2003, il enseigne à l’Institut de technologie de Géorgie (Georgia Tech) à Atlanta (Géorgie, États-Unis), avant de rejoindre l’université de New York où il est professeur à l’Institut Courant de sciences mathématiques depuis 2007.

C’est pendant ses années de doctorant, en 2002, que Khot énonce la conjecture des jeux uniques (U.G.C. pour unique games conjecture). Selon cette conjecture, pour une certaine classe de problèmes (appelés jeux uniques), il est NP-difficile de décider si l'on peut trouver une solution proche de l'optimale, ou si toutes les solutions sont loin de l'optimale. En théorie de la complexité, NP désigne les problèmes solubles en temps polynomiaux sur une machine de Turing non déterministe. Dire qu’un problème est NP-difficile signifie qu’il est au moins aussi difficile que tout problème NP connu. Cette conjecture généralise le théorème P.C.P. (probabilisticallycheckable proof, « preuve vérifiable de façon statistique »), établi en 1990-1992, qui affirme que tout problème de décision appartenant à la classe NP a une preuve qui peut être vérifiée par un algorithme contenant des tirages aléatoires. Autrement dit, il suffit de lire un nombre constant de bits choisis au hasard suivant une distribution adéquate d’une solution d’un problème NP pour décider si cette solution est valide.

L’U.G.C. est rapidement devenue un problème ouvert des plus importants dans la théorie de la complexité et de l'approximation. Khot et divers collaborateurs ont démontré que la difficulté de ces « jeux uniques » caractérisait le meilleur degré d’approximation qu’on pouvait espérer atteindre dans de nombreux problèmes d’optimisation. Ils en ont déduit de nouveaux théorèmes de limite centrale, des propriétés d’invariance et divers autres résultats qui leur ont permis de concevoir des méthodes originales utiles à la construction d’algorithmes de programmation très performants.

En 2014, Khot reçoit le prix Nevanlinna, considéré comme le « prix Nobel » en théorie de l’information, décerné une fois tous les quatre ans à un jeune informaticien. Selon la citation de cette prestigieuse récompense, Subhash Khot est distingué pour « sa définition visionnaire du problème des jeux uniques et son rôle de leader dans les efforts pour comprendre sa complexité, et pour son rôle central dans l’étude de problèmes d’approximation efficaces, qui ont produit des avancées majeures dans la conception d’algorithmes et dans la question de la difficulté de l’approximation, et pour de nouvelles interactions entre la complexité des calculs, l’analyse et la géométrie ». Bien que l’on ne sache pas encore si la conjecture est vraie, fausse ou indémontrable, son introduction a ouvert un riche domaine de la théorie de l’information.

— Bernard PIRE