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?
9
Respuestas:
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 ) .δ F O ( 1 ) F O ( δ- 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 ∈yon f( f) = n ⋅ Prx , i[ f( x ) ≠ f( x + eyo) ] PrX,i[f( x)≠f( x +ei) ] δ entre las coordenadas restantes, y arreglando al azar todo, excepto x i .i ∈ [ n ] 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δ F O ( 1 ) δ F r = O ( 1 ) δnorte δ F r . Porlotanto,Inf(f)=n⋅Prx,i[f(x)≠f(x+ei)]≤rrδnorte , según se requiera.yon f( f) = n ⋅ Prx , i[ f( x ) ≠ f( x + eyo) ] ≤ rδ
Observación: El reclamo anterior es estricto al tomar una función de paridad enbits O ( 1 / δ ) .O ( 1 / δ)
fuente