Abstract:
Assume that we have a Boolean function $\tilde{f}(x_0,\dots, x_{n-1})$ which in reality depends only on $m$ variables: $\tilde{f}(x_0,\dots, x_{n-1})\equiv f(x_{i_1}\dots,x_{i_m})$. Function $f$ is known, but the numbers of the significant variables $i_1,\dots,i_m$ are not. We wish to determine these numbers. In one check we can learn the value of $\tilde{f}(x_0,\dots, x_{n-1})$ for an arbitrary combination of variables $x_0,\dots, x_{n-1}$. The paper offers bounds for the number of checks over which the numbers$i_1,\dots,i_m$ can be found with certainty, and also some specific algorithms for finding these numbers.
Fulltext:
PDF file (2204 kB)