ECCC-Report TR10-061https://eccc.weizmann.ac.il/report/2010/061Comments and Revisions published for TR10-061en-usSat, 19 Jun 2010 14:32:00 +0300
Revision 2
| On Testing Computability by Small Width OBDDs |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2010/061#revision2We 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)$.
Sat, 19 Jun 2010 14:32:00 +0300https://eccc.weizmann.ac.il/report/2010/061#revision2
Revision 1
| On Testing Computability by Small Width OBDDs |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2010/061#revision1We 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)$.
Wed, 14 Apr 2010 17:16:47 +0300https://eccc.weizmann.ac.il/report/2010/061#revision1
Paper TR10-061
| On Testing Computability by Small Width OBDDs |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2010/061We 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)$.
Sat, 10 Apr 2010 14:21:52 +0300https://eccc.weizmann.ac.il/report/2010/061