Restrictions aléatoires et lien avec l'influence totale des fonctions booléennes

Disons que nous avons une fonction booléenne et que nous appliquons une restriction aléatoire δ sur f . De plus, disons que l'arbre de décision T qui calcule f se réduit à la taille O ( 1 ) en raison de la restriction aléatoire. Est-ce à dire que f a une influence totale très faible?$f:\{-1,1\}^n\rightarrow \{-1,1\}$$\delta$$f$$T$$f$$O(1)$$f$

Affirmation : Si la restriction aléatoire de f a un arbre de décision de taille O ( 1 ) (en attente), alors l'influence totale de ce f est O ( δ - 1 ) .$\delta$$f$$O(1)$$f$$O(\delta^{-1})$

Pr x , i [ f ( x ) ≠ f ( x + e i ) ] δ i ∈ [ n ] x $Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)]$$\Pr_{x,i}[f(x) \neq f(x+e_i)]$$\delta$$i \in [n]$$x_i$

Maintenant, si -restriction réduit l'arbre de décision de à la taille , alors en particulier la -restriction de dépend de coordonné. Prenons maintenant une coordonnée non fixe aléatoire (parmi ), et fixons toutes les autres au hasard. Puisque la restriction de dépend au plus de coordonnées , nous obtenons une fonction (sur un bit) qui n'est pas constante avec probabilité au plus . Par conséquent , comme requis.f O ( 1 ) δ f r = O ( 1 ) δ n δ f r $\delta$$f$$O(1)$$\delta$$f$$r = O(1)$$\delta n$$\delta$$f$$r$ Inf(f)=n⋅Prx,i[f(x)≠f(x+ei)]≤$\frac{r}{\delta n}$$Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)] \leq \frac{r}{\delta}$

Remarque: La revendication ci-dessus est serrée en prenant une fonction de parité sur les bits .$O(1/\delta)$