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:

\BE

\item

Testing whether $f:\{0,1\}^n\to\{0,1\}$ is implemented by

a width-4 OBDD requires $\Omega(\sqrt{n})$ queries.

\item

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.

\item

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.

\EE

Recall that each of these classes has a proper learning

algorithm of query complexity $O(n)$.

Added a new subsection (new Sec. 1.4).

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:

\BE

\item

Testing whether $f:\{0,1\}^n\to\{0,1\}$ is implemented by

a width-4 OBDD requires $\Omega(\sqrt{n})$ queries.

\item

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.

\item

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.

\EE

Recall that each of these classes has a proper learning

algorithm of query complexity $O(n)$.

correcting various typos

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:

\BE

\item

Testing whether $f:\{0,1\}^n\to\{0,1\}$ is implemented by

a width-4 OBDD requires $\Omega(\sqrt{n})$ queries.

\item

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.

\item

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.

\EE

Recall that each of these classes has a proper learning

algorithm of query complexity $O(n)$.