Aller au contenu principal

De l'hypercube à la sensitivité

01 avril 2021
Numéros de page :
pp.82-87
La "conjecture de la sensitivité", qui portait sur la complexité des fonctions booléennes, importantes en informatique, résistait depuis plusieurs décennies. Un jeune mathématicien d'origine chinoise, Hao Huang, l'a prouvée en deux pages, en exploitant un détour par les hypercubes.