7
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ It's certainly between $2^k$ and $2^k + O(k\log d)$. $\endgroup$ – Sasho Nikolov Aug 23 '16 at 0:21
  • $\begingroup$ @SashoNikolov Thanks. What is $d$? would you please elaborate a bit why you're certain? $\endgroup$ – seteropere Aug 23 '16 at 0:29
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Aug 23 '16 at 1:16
  • $\begingroup$ @AndrewMorgan why not turn your comment into an answer? $\endgroup$ – Aryeh Aug 23 '16 at 5:59
  • $\begingroup$ @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. $\endgroup$ – Andrew Morgan Aug 23 '16 at 6:35
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)}? $\endgroup$ – domotorp Aug 25 '16 at 9:36
  • $\begingroup$ 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. $\endgroup$ – Andrew Morgan Aug 25 '16 at 16:23
  • 1
    $\begingroup$ @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\}$). $\endgroup$ – Andrew Morgan Aug 25 '16 at 19:32
  • 1
    $\begingroup$ 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$. $\endgroup$ – Andrew Morgan Aug 25 '16 at 19:34
  • 2
    $\begingroup$ 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}$$ $\endgroup$ – domotorp Aug 25 '16 at 20:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.