| Résume | Imaginons un vote de N participants, qui prend la valeur 1 si la majorité a répondu oui, et la valeur -1 sinon. Le résultat du vote va-t-il etre modifié si une erreur de transmission est commise sur une fraction epsilon des N participants ? La plupart du temps, non. On dira que la fonction "Majorité" est stable, ou insensible "au bruit". (A l'inverse, en physique statistique, certaines configurations géométriques, définies en se plaçant au paramètre critique, sont hautement sensibles à de petites modifications locales. ) Une des premières "mesures" proposées pour quantifier "la complexité" d'une fonction booléenne, est la sensibilité dite locale, notée s(f), introduite par Cook et Dwork lors de leur étude de certains processeurs appelés CREW PRAM. Peu de temps après, Noam Nisan propose une autre mesure, la sensibilité par blocs, qui caractérise la difficulté de calcul qui intéressait Cook et Dwork. Depuis, cette dernière a été montrée polynomialement équivalente à d'autres mesures de complexité, telles que la complexité par certificat, celle par arbre de décision, ... Pendant des dizaines d'années, personne ne parvenait à montrer que la sensibilité locale s(f) était elle aussi dans cette classe d'équivalence (cette appartenance conjecturée s'appelle conjecture de Nisan et Szegedy). Par un argument simple et joli de théorie des graphes, et en utilisant une reformulation combinatoire de la conjecture (due à Gotsman et Linial), H. Huang a finalement prouvé la conjecture de Nisan et Szegedy : nous discuterons sa preuve après avoir introduit les différentes notions. |
