We take another step in the study of the testability of small-width OBDDs, initiated by Ron and Tsur (Random'09). That is, we consider algorithms that, given oracle access to a function $f:\{0,1\}^n\to\{0,1\}$, need to determine whether $f$ can be implemented by some restricted class of OBDDs or is far from any such function.

Ron and Tsur showed that testing whether a function $f:\{0,1\}^n\to\{0,1\}$ is implemented by a width-2 OBDD has query complexity $\Theta(\log n)$. Thus, testing width-2 OBDD functions is significantly easier than learning such functions (which requires $\Omega(n)$ queries). We show that such exponential gaps do not hold for several related classes. Specifically:

- Testing whether $f:\{0,1\}^n\to\{0,1\}$ is implemented by a width-4 OBDD requires $\Omega(\sqrt{n})$ queries.
- Testing whether $f:GF(3)^n\to GF(3)$ is a linear function with 0-1 coefficients requires $\Omega(\sqrt{n})$ queries. Note that this class of functions is a subset of the class of all linear functions over $GF(3)$, and that each such linear function can be implemented by a width-3 OBDD.
- There exists a subclass $\cal C$ of the linear functions from $GF(2)^n$ to $GF(2)$ such that testing membership in $\cal C$ has query complexity $\Theta({n})$. Note that each linear function over $GF(2)$ can be implemented by a width-2 OBDD.

While Section 2.2 is stated as referring to the task of testing
whether the number of influential variables (in a lineare function)
is *at most* $n/2$, it actually establishes the same results for
the case that the number of influential variables is *exactly* $n/2$.

Interestingly, as noted by Sourav Chakraborty, David Garcia-Soriano, and Arie Matsliah (private communcation of a few months ago), it is easy to prove an Omega(n/\log n) lower bound as follows:

- By Corollary 2.2,
*determining*the number of influential variables modulo 3 required Omega(n) queries. - Thus,
*determining*the actual number of influential variables required Omega(n) queries. - It follows that testing the
*at most $n/2$ influential variables*requires Omega(n/\log n) queries, because otherwise you derive a contradiction to (2) by a binary search.

The third paragraph in Section 1.4 (which is a conceptual discussion) contains a factual error (which is due to confusing the complexity of deciding the property with the complexity of implementing functions that satisfy the property). In any case, the functions presented in [10, 11] can be implemented by circuits of size that is polynomially related to the query complexity, $q$. These circuits may have depth that is polylogarithmic in $q$, but not such a size...

- First version posted: April 2010.
- Revisions: April 2010, June 2010.
- Presentation at RANDOM'10 (in PPT format).

Back to either Oded Goldreich's homepage or general list of papers.