On Testing Computability by Small Width OBDDs

Webpage for a paper by Oded Goldreich

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:

  1. Testing whether $f:\{0,1\}^n\to\{0,1\}$ is implemented by a width-4 OBDD requires $\Omega(\sqrt{n})$ queries.
  2. 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.
  3. 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.
Recall that each of these classes has a proper learning algorithm of query complexity $O(n)$.

Comment (added on March 2nd, 2011)

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:

  1. By Corollary 2.2, determining the number of influential variables modulo 3 required Omega(n) queries.
  2. Thus, determining the actual number of influential variables required Omega(n) queries.
  3. 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.

Errata (added on March 3rd, 2011)

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...

Material available on-line

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