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