Restricciones aleatorias y la conexión a la influencia total de las funciones booleanas.

9

Digamos que tenemos una función booleana y aplicamos restricción aleatoria δ en f . Además, supongamos que el árbol de decisión T que calcula f se reduce al tamaño O ( 1 ) como resultado de la restricción aleatoria. ¿Esto implica que f tiene una influencia total muy baja?F:{-1,1}norte{-1,1}δFTFO(1)F

Amit Levi
fuente
es una constante entre 0 y 1 y no depende de n? δ
Kaveh
1
Si. De hecho, . δ[0 0,1]
Amit Levi
1
No estoy seguro de si eso es lo que está buscando, pero por el lema de conmutación, si una función puede representarse con un DNF de ancho pequeño, entonces se reduciría a un árbol de decisión de tamaño constante. Los DNF de ancho pequeño tienen una influencia total baja, y uno puede expresar árboles de decisión a través de los DNF, por lo que moralmente parece que este es el caso.

Respuestas:

4

Reclamación: Si la restricción aleatoria de f tiene un árbol de decisión de tamaño O ( 1 ) (en expectativa), entonces la influencia total de tal f es O ( δ - 1 ) .δFO(1)FO(δ-1)

Bosquejo de prueba: por definición de influencia tenemos . Hagamos un límite superior de Pr x , i [ f ( x ) f ( x + e i ) ] aplicando primero una restricción δ , luego seleccionando i yonorteF(F)=nortePrX,yo[F(X)F(X+miyo)]Prx,yo[F(X)F(X+miyo)]δ entre las coordenadas restantes, y arreglando al azar todo, excepto x i .yo[norte]Xyo

Ahora, si la restricción reduce el árbol de decisión de f al tamaño O ( 1 ) , entonces, en particular, la restricción δ de f depende de r = O ( 1 ) coordinado. Elija ahora una coordenada no fija aleatoria (entre δ n ) y arreglemos todas las demás al azar. Dado que la restricción δ de f depende de la mayoría de las coordenadas r , obtenemos una función (en un bit) que no es constante con probabilidad como máximo rδFO(1)δFr=O(1)δnorteδFr . Porlotanto,Inf(f)=nPrx,i[f(x)f(x+ei)]rrδnorte , según se requiera.yonorteF(F)=nortePrX,yo[F(X)F(X+miyo)]rδ

Observación: El reclamo anterior es estricto al tomar una función de paridad enbits O ( 1 / δ ) .O(1/ /δ)

Igor Shinkar
fuente