We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter \varepsilon. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in \varepsilon ^{- 1}. The first test is stronger in that it has a 1-sided error, while the second test has a more compact analysis. We also present an adaptive version and a 2-sided error version of the first test, that have a somewhat better query complexity than the other algorithms.

We then provide a lower bound of \bar \Omega (\sqrt k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of \Omega (\log (k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group {\rm Z}_2^9 that may be interesting in its own right. We show that for some t(q) = \bar 0(q^2) the distributions of the random walk at times t and t + 2 are close to each other, independently of the step distribution of the walk.

We also discuss related questions. In particular, when given in advance a known k-junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in k and \varepsilon.