16
$\begingroup$

We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables.

Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by $x_1, x_2, \ldots, x_n$. Fix $$S_1 = \left\{ x_1, x_2, \ldots, x_{\frac{n}{2}} \right\},\quad S_2 = \left\{ x_{\frac{n}{2} + 1}, x_{\frac{n}{2} + 2}, \ldots, x_n \right\}.$$ Clearly, there exists $S \in \{S_1, S_2\}$ such that $S$ contains at least $k$ of the influencing variables of $f$.

Now let $\epsilon > 0$, and assume that $f: \{0,1\}^n \to \{0,1\}$ is $\epsilon$-far from every $2k$-junta (i.e., one has to change a fraction of at least $\epsilon$ of the values of $f$ in order to make it a $2k$-junta). Can we make a "robust" version of the statement above? That is, is there a universal constant $c$, and a set $S \in \{S_1, S_2\}$ such that $f$ is $\frac{\epsilon}{c}$-far from every function that contains at most $k$ influencing variables in $S$?

Note: In the original formulation of the question, $c$ was fixed as $2$. Neal's example shows that such value of $c$ does not suffice. However, since in property testing we are usually not too concerned with constants, I relaxed the condition a bit.

$\endgroup$
  • $\begingroup$ Can you clarify your terms? Is a variable "influencing" unless the value of f is always independent of the variable? Does "change a value of $f$" mean, change one of the values $f(x)$ for some particular $x$? $\endgroup$ – Neal Young Nov 17 '12 at 17:10
  • $\begingroup$ Of course, the variable $x_i$ is influencing if there exists an $n$-bit string $y$ such that $f(y) \neq f(y')$, where $y'$ is the string $y$ with its $i$'th coordinate flipped. Changing the value of $f$ means making a change in its truth table. $\endgroup$ – user887 Nov 17 '12 at 17:41
17
+50
$\begingroup$

The answer is “yes”. The proof is by contradiction.

For notational convenience, let us denote the first $n/2$ variables by $x$ and the second $n/2$ variables by $y$. Suppose that $f(x,y)$ is $\delta$-close to a function $f_1(x,y)$ which depends only on $k$ coordinates of $x$. Denote its influential coordinates by $T_1$. Similarly, suppose that $f(x,y)$ is $\delta$-close to a function $f_2(x,y)$ which depends only on $k$ coordinates of $y$. Denote its influential coordinates by $T_2$. We need to prove that $f$ is $4\delta$- close to a $2k$-junta $\tilde f(x,y)$.

Let us say that $(x_1,y_1) \sim (x_2,y_2)$ if $x_1$ and $x_2$ agree on all coordinates in $T_1$ and $y_1$ and $y_2$ agree on all coordinates in $T_2$. We choose uniformly at random a representative from each equivalence class. Let $(\bar x, \bar y)$ be the representative for the class of $(x,y)$. Define $\tilde f$ as follows: $$\tilde f(x,y) = f(\bar x, \bar y).$$

It is obvious that $\tilde f$ is a $2k$-junta (it depends only on variables in $T_1 \cup T_2)$. We shall prove that it is at distance $4\delta$ from $f$ in expectation.

We want to prove that $$\Pr_{\tilde f}(\Pr_{x,y}(\tilde f(x,y) \neq f(x,y))) = \Pr(f(\bar x, \bar y) \neq f(x,y)) \leq 4\delta,$$ where $x$ and $y$ are chosen uniformly at random. Consider a random vector $\tilde x$ obtained from $x$ by keeping all bits in $T_1$ and randomly flipping all bits not in $T_1$, and a vector $\tilde y$ defined similarly. Note that $$\Pr(\tilde f(x,y) \neq f(x,y)) = \Pr(f(\bar x, \bar y) \neq f(x,y))= \Pr(f(\tilde x, \tilde y) \neq f(x,y)).$$

We have, $$\Pr(f(x,y) \neq f(\tilde x, y)) \leq \Pr(f(x,y) \neq f_1(x, y)) + \Pr(f_1(x,y) \neq f_1(\tilde x, y)) + \Pr(f_1(\tilde x,y) \neq f(\tilde x, y)) \leq \delta + 0 + \delta = 2\delta.$$

Similarly, $\Pr(f(\tilde x,y) \neq f(\tilde x, \tilde y)) \leq 2\delta$. We have $$\Pr(f(\bar x, \bar y) \neq f(x,y)) \leq 4\delta.$$ QED

It easy to “derandomize” this proof. For every $(x,y)$, let $\tilde f(x,y) = 1$ if $f(x,y) = 1$ for most $(x',y')$ in the equivalence class of $(x,y)$, and $\tilde f(x,y) = 0$, otherwise.

$\endgroup$
12
$\begingroup$

The smallest $c$ that the bound holds for is $c = \frac{1}{\sqrt 2 - 1} \approx 2.41$.

Lemmas 1 and 2 show that the bound holds for this $c$. Lemma 3 shows that this bound is tight.

(In comparison, Juri's elegant probabilistic argument gives $c=4$.)

Let $c=\frac{1}{\sqrt 2 - 1}$. Lemma 1 gives the upper bound for $k=0$.

Lemma 1: If $f$ is $\epsilon_g$-near a function $g$ that has no influencing variables in $S_2$, and $f$ is $\epsilon_h$-near a function $h$ that has no influencing variables in $S_1$, then $f$ is $\epsilon$-near a constant function, where $\epsilon \le \frac{(\epsilon_g+\epsilon_h)/2}{c}$.

Proof. Let $\epsilon$ be the distance from $f$ to a constant function. Suppose for contradiction that $\epsilon$ does not satisfy the claimed inequality. Let $y=(x_1,x_2,\ldots,x_{n/2})$ and $z=(x_{n/2}+1,\ldots,x_n)$ and write $f$, $g$, and $h$ as $f(y,z)$, $g(y,z)$ and $h(y,z)$, so $g(y,z)$ is independent of $z$ and $h(y,z)$ is independent of $y$.

(I find it helpful to visualize $f$ as the edge-labeling of the complete bipartite graph with vertex sets $\{y\}$ and $\{z\}$, where $g$ gives a vertex-labeling of $\{y\}$, and $h$ gives a vertex-labeling of $\{z\}$.)

Let $g_0$ be the fraction of pairs $(y,z)$ such that $g(y,z) = 0$. Let $g_1=1-g_0$ be the fraction of pairs such that $g(y,z) = 1$. Likewise let $h_0$ be the fraction of pairs such that $h(y,z) = 0$, and let $h_1$ 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 $\epsilon_g$ and $\epsilon_h$ by $1/2^n$, while decreasing the $\epsilon$ by at most $1/2^n$, 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, $\epsilon_g + \epsilon_h = g_0 h_1 + g_1 h_0$.

The distance from $f$ to the all-zero function is at most $1 - g_0 h_0$.

The distance from $f$ to the all-ones function is at most $1-g_1 h_1$.

Further, the distance from $f$ to the nearest constant function is at most $1/2$.

Thus, the ratio $\epsilon/(\epsilon_g+\epsilon_h)$ is at most $$\frac{\min(1/2, 1-g_0 h_0, 1-g_1 h_1)}{g_0 h_1 + g_1 h_0},$$ where $g_0,h_0 \in [0,1]$ and $g_1 = 1-g_0$ and $h_1=1-h_0$.

By calculation, this ratio is at most $\frac{1}{2(\sqrt 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=\frac{1}{\sqrt 2 - 1}$.

Lemma 2: Fix any $k$. If $f$ is $\epsilon_g$-near a function $g$ that has $k$ influencing variables in $S_2$, and $f$ is $\epsilon_h$-near a function $h$ that has $k$ influencing variables in $S_1$, then $f$ is $\epsilon$-near a function $\hat f$ that has at most $2k$ influencing variables, where $\epsilon \le \frac{(\epsilon_g+\epsilon_h)/2}{c}$.

Proof. Express $f$ as $f(a,y,b,z)$ where $(a,y)$ contains the variables in $S_1$ with $a$ containing those that influence $h$, while $(b,z)$ contains the variables in $S_2$ 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 $F_{ab}(y,z) = f(a,y,b,z)$, and define $G_{ab}$ and $H_{ab}$ similarly from $g$ and $h$ respectively. Let $\epsilon^g_{ab}$ be the distance from $F_{ab}$ to $G_{ab}$ (restricted to $(y,z)$ pairs). Likewise let $\epsilon^h_{ab}$ be the distance from $F_{ab}$ to $H_{ab}$.

By Lemma 1, there exists a constant $c_{ab}$ such that the distance (call it $\epsilon_{ab}$) from $F_{ab}$ to the constant function $c_{ab}$ is at most $(\epsilon^h_{ab} + \epsilon^g_{ab})/(2c)$. Define $\hat f(a,y,b,z) = c_{ab}$.

Clearly $\hat f$ depends only on $a$ and $b$ (and thus at most $k$ variables).

Let $\epsilon_{\hat f}$ be the average, over the $(a,b)$ pairs, of the $\epsilon_{ab}$'s, so that the distance from $f$ to $\hat f$ is $\epsilon_{\hat f}$.

Likewise, the distances from $f$ to $g$ and from $f$ to $h$ (that is, $\epsilon_g$ and $\epsilon_h)$ are the averages, over the $(a,b)$ pairs, of, respectively, $\epsilon^g_{ab}$ and $\epsilon^h_{ab}$.

Since $\epsilon_{ab} \le (\epsilon^h_{ab} + \epsilon^g_{ab})/(2c)$ for all $a, b$, it follows that $\epsilon_{\hat f} \le (\epsilon_g + \epsilon_h)/(2c)$. QED

Lemma 3 shows that the constant $c$ above is the best you can hope for (even for $k=0$ and $\epsilon=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 $S_2$ and $h$ has no influencing variables in $S_1$, and $f$ is $0.5$-far from every constant function.

Proof. Let $y$ and $z$ be $x$ restricted to, respectively, $S_1$ and $S_2$. That is, $y=(x_1,\ldots,x_{n/2})$ and $z=(x_{n/2+1},\ldots,x_n)$.

Identify each possible $y$ with a unique element of $[N]$, where $N=2^{n/2}$. Likewise, identify each possible $z$ with a unique element of $[N]$. Thus, we think of $f$ as a function from $[N]\times[N]$ to $\{0,1\}$.

Define $f(y,z)$ to be 1 iff $\max(y,z) \ge \frac{1}{\sqrt 2}N$.

By calculation, the fraction of $f$'s values that are zero is $(\frac{1}{\sqrt 2})^2 = \frac{1}{2}$, so both constant functions have distance $\frac{1}{2}$ to $f$.

Define $g(y,z)$ to be 1 iff $y\ge \frac{1}{\sqrt 2}N$. Then $g$ has no influencing variables in $S_2$. The distance from $f$ to $g$ is the fraction of pairs $(y,z)$ such that $y<\frac{1}{\sqrt 2}N$ and $z\ge \frac{1}{\sqrt 2}N$. By calculation, this is at most $\frac{1}{\sqrt 2}(1-\frac{1}{\sqrt2}) = 0.5/c$

Similarly, the distance from $f$ to $h$, where $h(y,z)=1$ iff $z\ge \frac{1}{\sqrt 2}N$, is at most $0.5/c$.

QED

$\endgroup$
  • $\begingroup$ First of all, thanks Neal! This indeed sums it up for $k=0$, and sheds some light on the general problem. However in the case of $k=0$ the problem is a bit degenerate (as $2k=k$), so I'm more curious regarding the case of $k \ge 1$. I didn't manage to extend this claim for $k>0$, so if you have an idea on how to do it - I'd appreciate it. If it simplifies the problem, then the exact constants are not crucial; that is, $\epsilon/2$-far can be replaced by $\epsilon/c$-far, for some universal constant $c$. $\endgroup$ – user887 Nov 18 '12 at 13:30
  • 2
    $\begingroup$ I've edited it to add the extension to general k. And Yuri's argument below gives a slightly looser factor with an elegant probabilistic argument. $\endgroup$ – Neal Young Nov 18 '12 at 16:09
  • $\begingroup$ Sincere thanks Neal! This line of reasoning is quite enlightening. $\endgroup$ – user887 Nov 18 '12 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy