ECCC-Report TR99-011https://eccc.weizmann.ac.il/report/1999/011Comments and Revisions published for TR99-011en-usWed, 14 Apr 1999 15:43:43 +0300
Paper TR99-011
| Approximations by OBDDs and the variable ordering problem |
Matthias Krause,
Petr Savicky,
Ingo Wegener
https://eccc.weizmann.ac.il/report/1999/011
Ordered binary decision diagrams (OBDDs) and their variants
are motivated by the need to represent Boolean functions
in applications. Research concerning these applications leads
also to problems and results interesting from theoretical
point of view. In this paper, methods from communication
complexity and information theory are combined to prove
that the direct storage access function and the inner product
function have the following property. They have linear
\pi-OBDD size for some variable ordering \pi and, for most
variable orderings \pi', all functions which approximate
them on considerably more than half of the inputs, need
exponential \pi'-OBDD size. These results have implications
for the use of OBDDs in experiments with genetic programming.
Wed, 14 Apr 1999 15:43:43 +0300https://eccc.weizmann.ac.il/report/1999/011