Fonctions Booléennes et percolation critique

vendredi 27 avril 2012, 11h00 - 12h00

Salle de réunion, espace Turing

{{Lieu}}

Salle des thèses (5ème étage, bâtiment Jacob)

{{Résumé}}

Du fait de leur omniprésence en informatique, leurs propriétés ont été étudiées abondamment depuis l’émergence de « l’informatique théorique ». Comme je tacherai de l’expliquer au cours de cet exposé, l’un des axes majeurs de l’étude de ces fonctions Booléennes est leur étude spectrale : de la m »me façon qu’une fonction périodique $g$ du cercle dans $R$ se décompose en séries de Fourier, il y a une façon naturelle et canonique de décomposer une fonction Booléenne $f$ en séries de Fourier. Le « spectre » ainsi obtenu pour la fonction $f$ en dit long sur les propriétés de cette dernière. Par exemple, une fonction Booléenne $ f=f(x_1,..x_n) $ de basse fréquence sera (en un sens précis) une fonction stable par rapport aux erreurs de transmission des « bits » $ x_i \in \{0,1\} $

.

Dans une deuxième partie de l’exposé, j’expliquerai en quoi l’étude
spectrale de certaines fonctions Booléennes permet de mettre en évidence
des propriétés surprenantes pour le modèle de la percolation critique dans le plan. Je ne supposerai aucun prérequis que ce soit du coté des fonctions Booléennes ou du coté du modèle de la percolation.