Summary: We show that a Boolean-valued function over \(n\) variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only \(J\) of them using a number of queries that depends only polynomially on \(J\) and the approximation parameter \(\varepsilon\). We present several tests that require a number of queries that is polynomial in \(J\) and linear in \(\varepsilon^{-1}\). We show a non-adaptive test that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over \(n\) Boolean variables, and has a more compact analysis.
We then provide a lower bound of \(\widetilde{\Omega}(\sqrt J)\) on the number of queries required for the non-adaptive testing of the above property; a lower bound of \(\Omega(\log(J+1))\) for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group \(Z^q_2\) that may be interesting in its own right. We show that for some \(t(q)=\widetilde O(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 \(J\)-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 \(J\) and \(\varepsilon^{-1}\).

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.