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é}}

$Une\; fonction\; Booléenne\; est\; un\; objet\; combinatoire\; très\; simple\; :\; il\; s’agit$
d’une fonction $ f : \{0,1\}^n -> \{0,1\} $.

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.