# What is the VC Dimension of the $k-$Junta class

A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension of this class?

Or at least is there any known method to construct the largest shattered set for small values of $k$ say when $k=1$.

• It's certainly between $2^k$ and $2^k + O(k\log d)$. – Sasho Nikolov Aug 23 '16 at 0:21
• @SashoNikolov Thanks. What is $d$? would you please elaborate a bit why you're certain? – seteropere Aug 23 '16 at 0:29
• sorry, $d$ should have been $n$. The $2^k$ lower bound is because you can shatter, for example, the points $\{x: x_{k+1} = \ldots = x_n = 0\}$ with the $k$-juntas that depend on $x_1, \ldots, x_k$. The upper bound is because VC-dimension is always at most log base 2 of the number of functions, and there are ${n\choose k}2^{2^k}$ many $k$-juntas: ${n \choose k}$ ways to pick $k$ coordinates and $2^{2^k}$ ways to pick the $2^k$ values of the coordinates. – Sasho Nikolov Aug 23 '16 at 1:16
• @AndrewMorgan why not turn your comment into an answer? – Aryeh Aug 23 '16 at 5:59
• @Aryeh I suppose I did answer part of the question, so I went ahead and moved my comment to an answer. Thanks for the recommendation. – Andrew Morgan Aug 23 '16 at 6:35

For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$.

The upper bound follows essentially from Sasho's argument: there are $2+2n$ 1-juntas on $n$ variables, and if there were more than $\log_2$ of that many inputs, we could find a function that avoids all 1-juntas.

To see the lower bound, consider the matrix whose columns contain the $2^{\lfloor \log_2(n+1) \rfloor} - 1 \le n$ not-all-zero bitstrings of length $\lfloor \log_2(n+1) \rfloor + 1$ that start with a zero. The inputs to shatter are the rows of this matrix (padded up to length $n$). Every function of these inputs is either constant, or else it or its negation appears as a column, so it's computed by a 1-junta.

Here's an example for the case $n=7$ which illustrates the general idea. The claim is that the VC dimension of $1$-juntas on $7$ bits is $4$. Consider the matrix

$$\begin{array}{ccccccc} 0&0&0&0&0&0&0\\ 1&0&0&0&1&1&1\\ 0&1&0&1&0&1&1\\ 0&0&1&1&1&0&1 \end{array}$$

formed by setting the columns to be all the length-$4$, not-all-zero bit strings that start with a zero. The claim is that the rows of this matrix are shattered by 1-juntas.

To see this, let $f$ be any boolean function of the rows. We can regard $f$ as a column. Now observe that either $f$ is constant, or else $f$ or its negation appears as some column in the matrix, simply by virtue of how we defined the matrix. In the first case, $f$ is obviously a 1-junta. In the latter case, suppose $f$ appears as column $i$, and observe that we can therefore compute $f$ as just the $i$-th dictator function. It follows that $f$ is again a 1-junta. A similar argument works when the negation of $f$ appears as a column--we represent $f$ by the negation of the $i$-th dictator. Thus in every case $f$ is a 1-junta. Since $f$ was arbitrary, it follows that the set formed by the rows of the above matrix is shattered by 1-juntas.

This idea can in theory be extended to larger $k$, where you encode every function as some $k$ columns in the matrix. I don't see how best to argue this at the moment, though.

• I'm sorry but I don't understand either your solution, or the problem itself. What are we trying to shatter, i.e., what are the points of the base set? I thought that it was the domain of $f$. If $n=2$, then how do you separate {(1,1)} from {(0,0),(0,1),(1.0)}? – domotorp Aug 25 '16 at 9:36
• Every function in the concept class shares a common domain $U$. "Shattered-ness" is a property of subsets of $U$: a subset is shattered if every function on that subset is a restriction of a function in the class. The VC dimension of the class is the size of the largest shattered set. So upper bounds are proven by showing every too-big subset has a function outside the class; lower bounds are proven by giving some set of points so that every function is in the class. In your final question, you've implicitly noticed that the subset of all 4 points is not shattered, because AND isn't a 1-junta. – Andrew Morgan Aug 25 '16 at 16:23
• @domotorp: I added an example where $n=7$ (chosen instead of $n=3$ since then $n$ and the VC dimension are different numbers). A more succinct answer to your question though is that, when $n=3$, the domain would just be $\{0,1\}^3$. I realize now that this wasn't explicit in the question, but you can make the domain larger (say $\mathbb{R}^n$) and this can only make the VC dimension larger (as long as the codomain is still $\{0,1\}$). – Andrew Morgan Aug 25 '16 at 19:32
• I suppose you might object that a dictator $\mathbb{R}^n\to\{0,1\}$ can be any function that depends on only one coordinate, and this would severely break the upper bound argument. I'll add a disclaimer to my answer, but I think OP will most likely be interested in the case when the domain is $\{0,1\}^n$. – Andrew Morgan Aug 25 '16 at 19:34
• Thanks, now everything is clear. Moreover, I believe that in a similar way one can obtain the optimal $O(k\log n)$ bound mentioned by Sasho. All you have to do is take $k$ copies of this matrix diagonally, so like $$\begin{array}{cccccccccccccc} 0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&0&0&1&1&1&0&0&0&0&0&0&0\\ 0&1&0&1&0&1&1&0&0&0&0&0&0&0\\ 0&0&1&1&1&0&1&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&1&0&0&0&1&1&1\\ 0&0&0&0&0&0&0&0&1&0&1&0&1&1\\ 0&0&0&0&0&0&0&0&0&1&1&1&0&1 \end{array}$$ – domotorp Aug 25 '16 at 20:39