Restrições aleatórias e a conexão com a influência total das funções booleanas

9

Digamos que temos uma função booleana f:{-1 1,1 1}n{-1 1,1 1} e aplicamos a restrição aleatória δ em f . Além disso, diga que a árvore de decisão T que calcula f diminui para o tamanho O(1 1) como resultado da restrição aleatória. Isso implica que f tem uma influência total muito baixa?

Amit Levi
fonte
δ é uma constante entre 0 e 1 e não depende de n?
Kaveh
11
Sim. De fato δ[0,1] .
Amit Levi
11
Não tenho certeza se é isso que você está procurando, mas pelo lema de comutação, se uma função pode ser representada por um DNF de largura pequena, então o que diminuiria para uma árvore de decisão de tamanho constante. DNFs de largura pequena têm baixa influência total e pode-se expressar árvores de decisão via DNFs; portanto, moralmente parece que esse é o caso.

Respostas:

4

Reivindicação: Se a restrição aleatória de f tem uma árvore de decisão do tamanho O ( 1 ) (em expectativa), então a influência total de tal f é O ( δ - 1 ) .δfO(1)fO(δ1)

Esboço prova: Por definição de influência que temos . Vamos limite superior Pr x , i [ f ( x ) f ( x + e i ) ] em primeiro lugar, aplicando uma δ -restriction, em seguida, escolhendo i Inf(f)=nPrx,i[f(x)f(x+ei)]Prx,i[f(x)f(x+ei)]δ entre as coordenadas restantes, e corrigindo aleatoriamente tudo, exceto x i .i[n]xi

Agora, se a restrição de reduz a árvore de decisão de f para o tamanho O ( 1 ) , em particular a restrição de δ de f depende de r = O ( 1 ) coordenado. Vamos agora escolher uma coordenada não fixa aleatória (entre δ n ) e corrigir todas as outras aleatoriamente. Como a restrição de δ de f depende de no máximo r coordenadas, obtemos uma função (em um bit) que não é constante com probabilidade no máximo rδfO(1)δfr=O(1)δnδfr . PortantoInf(f)=nPrx,i[f(x)f(x+ei)]rrδn , conforme necessário.Inf(f)=nPrx,i[f(x)f(x+ei)]rδ

Observação: a reivindicação acima é rigorosa ao assumir uma função de paridade nos bits .O(1/δ)

Igor Shinkar
fonte