Méthodes d'analyse dans l'étude des fonctions booléennes

 

Hamed Hatami

Université McGill

 

Domaine : structures abstraites

Programme établissement de nouveaux chercheurs universitaires

Concours 2011-2012

L'influence d'une variable sur une fonction booléenne mesure la sensibilité de la fonction par rapport aux changements de cette variable. Cette notion fondamentale qui se pose naturellement dans des nombreux domaines comme la physique statistique et la théorie des probabilités (par exemple, la transition de phase, percolation), l'informatique (par exemple, la théorie de la complexité), la combinatoire (par exemple, les produits de graphes), l'économie (par exemple, des choix sociaux, l'agrégation de l'information).

Il y a beaucoup de problèmes importants concernant les influences et l'analyse de Fourier des fonctions booléennes qui sont restés sans solutions. Une fois ces problèmes résolus, on aurait de nombreuses applications en combinatoire et en informatique théorique. Par exemple, une réponse affirmative à la conjecture entropie/influence de Friedgut et Kalai donnerait des preuves unifiées aux quelques résultats importants connus, et cela impliquerait des nouveaux résultats comme une conjecture de Y. Mansour.

Je vais me concentrer sur la résolution de certains de ces problèmes. Il existe plusieurs sous-problèmes ou des problèmes intermédiaires qui seront des grands projets pour les étudiants gradués.