Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-061 | 19th June 2010 14:31

On Testing Computability by Small Width OBDDs

RSS-Feed




Revision #2
Authors: Oded Goldreich
Accepted on: 19th June 2010 14:32
Downloads: 2606
Keywords: 


Abstract:

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



Changes to previous version:

Added a new subsection (new Sec. 1.4).


Revision #1 to TR10-061 | 14th April 2010 17:16

On Testing Computability by Small Width OBDDs





Revision #1
Authors: Oded Goldreich
Accepted on: 14th April 2010 17:16
Downloads: 2727
Keywords: 


Abstract:

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



Changes to previous version:

correcting various typos


Paper:

TR10-061 | 10th April 2010 14:21

On Testing Computability by Small Width OBDDs





TR10-061
Authors: Oded Goldreich
Publication: 10th April 2010 14:21
Downloads: 3376
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint