Testing juntas [combinatorial property testing]

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 ε. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in ε^-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 Ω˜(√ k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of Ω(log(k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group Z₂^q that may be interesting in its own right. We show that for some t(q) = O˜(q²), 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 ε.