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.
Robustness of splitting a junta
co.combinatorics;boolean functions;fourier analysis;property testing
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.$$QEDIt 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.