Decimos que una función booleana f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1} es una kk -junta si ff tiene como máximo kk variables de influencia.
Sea f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1} ser un 2 k2k -junta. Denote las variables de ff por x 1 , x 2 , ... , x nx1,x2,…,xn . Arreglo
S 1 = { x 1 , x 2 , … , x n2 },S 2 = { x n2 +1,xn2 +2,...,xn}.
S1={x1,x2,…,xn2},S2={xn2+1,xn2+2,…,xn}.
Claramente, existe
S∈{S1,S2}S∈{S1,S2}tal que
SScontiene al menos
kkde las variables influyentes de
ff.
Ahora deje ϵ > 0ϵ>0 , y suponga que f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1} es ϵϵ -mucho de cada 2 k2k -junta (es decir, uno tiene que cambiar una fracción de al menos ϵϵ de los valores de ff para que sea un 2 k2k -junta). ¿Podemos hacer una versión "robusta" de la declaración anterior? Es decir, ¿hay una constante universal cc , y un conjunto S ∈ { S 1 , S 2 }S∈{S1,S2}tal que ff es ϵc: ¿ϵc lejos de cada función que contiene como máximokkvariables influyentes enSS?
Nota: En la formulación original de la pregunta, cc se fijó como 22 . El ejemplo de Neal muestra que dicho valor de cc no es suficiente. Sin embargo, dado que en las pruebas de propiedad generalmente no nos preocupamos demasiado por las constantes, relajé un poco la condición.
Respuestas:
La respuesta es sí". La prueba es por contradiccion.
Por conveniencia de notación, denotemos las primeras n / 2n/2 variables por xx y las segundas n / 2n/2 variables por yy . Suponga que f ( x , y )f(x,y) es δδ -cierre a una función f 1 ( x , y )f1(x,y) que depende solo de las coordenadas kk de xx . Denota sus coordenadas influyentes por T 1T1 . Del mismo modo, supongamos que f ( x , y )f(x,y) esδ - cerca de una función f 2 ( x , y ) que depende solo de lascoordenadas k de y . Denota sus coordenadas influyentes por T 2 . Necesitamos demostrar que f es 4 δ - cerca de 2 k -junta ˜ f ( x , y ) .δ f2(x,y) k y T2 f 4δ 2k f~(x,y)
Digamos que ( x 1 , y 1 ) ∼ ( x 2 , y 2 ) si x 1 y x 2 están de acuerdo en todas las coordenadas en T 1 e y 1 e y 2 están de acuerdo en todas las coordenadas en T 2 . Elegimos uniformemente al azar un representante de cada clase de equivalencia. Sea ( ˉ x , ˉ y ) el representante de la clase de ( x ,(x1,y1)∼(x2,y2) x1 x2 T1 y1 y2 T2 (x¯,y¯) y)(x,y) . Define ˜ff~ as follows:
˜f(x,y)=f(ˉx,ˉy).
It is obvious that ˜ff~ is a 2k2k -junta (it depends only on variables in T1∪T2)T1∪T2) . We shall prove that it is at distance 4δ4δ from ff in expectation.
We want to prove that Pr˜f(Prx,y(˜f(x,y)≠f(x,y)))=Pr(f(ˉx,ˉy)≠f(x,y))≤4δ,
We have, Pr(f(x,y)≠f(˜x,y))≤Pr(f(x,y)≠f1(x,y))+Pr(f1(x,y)≠f1(˜x,y))+Pr(f1(˜x,y)≠f(˜x,y))≤δ+0+δ=2δ.
Similarly, Pr(f(˜x,y)≠f(˜x,˜y))≤2δPr(f(x~,y)≠f(x~,y~))≤2δ . We have
Pr(f(ˉx,ˉy)≠f(x,y))≤4δ.
It easy to “derandomize” this proof. For every (x,y)(x,y) , let ˜f(x,y)=1f~(x,y)=1 if f(x,y)=1f(x,y)=1 for most (x′,y′)(x′,y′) in the equivalence class of (x,y)(x,y) , and ˜f(x,y)=0f~(x,y)=0 , otherwise.
fuente
The smallest cc that the bound holds for is c=1√2−1≈2.41c=12√−1≈2.41 .
Lemmas 1 and 2 show that the bound holds for this cc .
Lemma 3 shows that this bound is tight.
(In comparison, Juri's elegant probabilistic argument gives c=4c=4 .)
Let c=1√2−1c=12√−1 .
Lemma 1 gives the upper bound for k=0k=0 .
Lemma 1: If ff is ϵgϵg -near a function gg that has no influencing variables
in S2S2 , and ff is ϵhϵh -near a function hh that has no influencing variables
in S1S1 , then ff is ϵϵ -near a constant function,
where ϵ≤(ϵg+ϵh)/2cϵ≤(ϵg+ϵh)/2c .
Proof. Let ϵϵ be the distance from ff to a constant function.
Suppose for contradiction that ϵϵ does not satisfy the claimed inequality.
Let y=(x1,x2,…,xn/2)y=(x1,x2,…,xn/2) and z=(xn/2+1,…,xn)z=(xn/2+1,…,xn)
and write ff , gg , and hh as f(y,z)f(y,z) , g(y,z)g(y,z) and h(y,z)h(y,z) ,
so g(y,z)g(y,z) is independent of zz and h(y,z)h(y,z) is independent of yy .
(I find it helpful to visualize ff as the edge-labeling
of the complete bipartite graph with vertex sets {y}{y} and {z}{z} ,
where gg gives a vertex-labeling of {y}{y} ,
and hh gives a vertex-labeling of {z}{z} .)
Let g0g0 be the fraction of pairs (y,z)(y,z) such that g(y,z)=0g(y,z)=0 .
Let g1=1−g0 be the fraction of pairs such that g(y,z)=1.
Likewise let h0 be the fraction of pairs such that h(y,z)=0,
and let h1 be the fraction of pairs such that h(y,z)=1.
Without loss of generality, assume that, for any pair such that g(y,z)=h(y,z), it also holds that f(y,z)=g(y,z)=h(y,z). (Otherwise, toggling the value of f(y,z) allows us to decrease both ϵg and ϵh by 1/2n, while decreasing the ϵ by at most 1/2n, so the resulting function is still a counter-example.) Say any such pair is ``in agreement''.
The distance from f to g plus the distance from f to h is the fraction of (x,y) pairs that are not in agreement. That is, ϵg+ϵh=g0h1+g1h0.
The distance from f to the all-zero function is at most 1−g0h0.
The distance from f to the all-ones function is at most 1−g1h1.
Further, the distance from f to the nearest constant function is at most 1/2.
Thus, the ratio ϵ/(ϵg+ϵh) is at most min(1/2,1−g0h0,1−g1h1)g0h1+g1h0,
By calculation, this ratio is at most 12(√2−1)=c/2. QED
Lemma 2 extends Lemma 1 to general k by arguing pointwise, over every possible setting of the 2k influencing variables. Recall that c=1√2−1.
Lemma 2: Fix any k. If f is ϵg-near a function g that has k influencing variables in S2, and f is ϵh-near a function h that has k influencing variables in S1, then f is ϵ-near a function ˆf that has at most 2k influencing variables, where ϵ≤(ϵg+ϵh)/2c.
Proof. Express f as f(a,y,b,z) where (a,y) contains the variables in S1 with a containing those that influence h, while (b,z) contains the variables in S2 with b containing those influencing g. So g(a,y,b,z) is independent of z, and h(a,y,b,z) is independent of y.
For each fixed value of a and b, define Fab(y,z)=f(a,y,b,z), and define Gab and Hab similarly from g and h respectively. Let ϵgab be the distance from Fab to Gab (restricted to (y,z) pairs). Likewise let ϵhab be the distance from Fab to Hab.
By Lemma 1, there exists a constant cab such that the distance (call it ϵab) from Fab to the constant function cab is at most (ϵhab+ϵgab)/(2c). Define ˆf(a,y,b,z)=cab.
Clearly ˆf depends only on a and b (and thus at most k variables).
Let ϵˆf be the average, over the (a,b) pairs, of the ϵab's, so that the distance from f to ˆf is ϵˆf.
Likewise, the distances from f to g and from f to h (that is, ϵg and ϵh) are the averages, over the (a,b) pairs, of, respectively, ϵgab and ϵhab.
Since ϵab≤(ϵhab+ϵgab)/(2c) for all a,b, it follows that ϵˆf≤(ϵg+ϵh)/(2c). QED
Lemma 3 shows that the constant c above is the best you can hope for (even for k=0 and ϵ=0.5).
Lemma 3: There exists f such that f is (0.5/c)-near two functions g and h, where g has no influencing variables in S2 and h has no influencing variables in S1, and f is 0.5-far from every constant function.
Proof. Let y and z be x restricted to, respectively, S1 and S2. That is, y=(x1,…,xn/2) and z=(xn/2+1,…,xn).
Identify each possible y with a unique element of [N], where N=2n/2. Likewise, identify each possible z with a unique element of [N]. Thus, we think of f as a function from [N]×[N] to {0,1}.
Define f(y,z) to be 1 iff max(y,z)≥1√2N.
By calculation, the fraction of f's values that are zero is (1√2)2=12, so both constant functions have distance 12 to f.
Define g(y,z) to be 1 iff y≥1√2N. Then g has no influencing variables in S2. The distance from f to g is the fraction of pairs (y,z) such that y<1√2N and z≥1√2N. By calculation, this is at most 1√2(1−1√2)=0.5/c
Similarly, the distance from f to h, where h(y,z)=1 iff z≥1√2N, is at most 0.5/c.
QED
fuente