ECCC-Report TR11-041https://eccc.weizmann.ac.il/report/2011/041Comments and Revisions published for TR11-041en-usThu, 24 Mar 2011 15:55:33 +0200
Paper TR11-041
| Testing Computability by Width-Two OBDDs |
Dana Ron,
Gilad Tsur
https://eccc.weizmann.ac.il/report/2011/041Property testing is concerned with deciding whether an object
(e.g. a graph or a function) has a certain property or is ``far''
(for a prespecified distance measure) from every object with
that property. In this work we consider the property of being
computable by a read-once width-$2$ {\em Ordered Binary Decision Diagram}
(OBDD), also known as a {\em branching program\/}, in two settings.
In the first setting the order of the variables is fixed and given
to the algorithm, while in the second setting it is not fixed.
That is, while in the first setting we should accept a function
$f$ if it is computable by a width-$2$ OBDD with a {\em given\/}
order of the variables, in the second setting we should accept a
function $f$ if there {\em exists\/} an order of the variables
according to which a width-$2$ OBDD can compute $f$.
Width-$2$ OBDDs generalize two classes of functions that have been
studied in the context of property testing - linear functions
(over $GF(2)^n$) and monomials. In both these cases membership can
be tested by performing a number of queries that is {\em independent
of the number of variables, $n$\/} (and is linear in $1/\epsilon$,
where $\epsilon$ is the distance parameter). In contrast, we show
that testing computability by width-$2$ OBDDs when the order of variables
is fixed and known requires a number of queries that grows logarithmically
with $n$ (for a constant $\epsilon$), and we provide an algorithm that performs
$\tilde{O}(\log n/\epsilon)$ queries. For the case where the order is
not fixed, we show that there is {\em no\/} testing algorithm that performs
a number of queries that is sublinear in $n$.
Thu, 24 Mar 2011 15:55:33 +0200https://eccc.weizmann.ac.il/report/2011/041