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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Aug 25, 2016 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
    Commented Aug 25, 2016 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
    Commented Aug 25, 2016 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
    Commented Aug 25, 2016 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
    Commented Aug 25, 2016 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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