Approximations by OBDDs and the variable ordering problem


Krause, Matthias ; Savický, Petr ; Wegener, Ingo



URL: https://eccc.weizmann.ac.il/report/1999/011/
Additional URL: https://www.semanticscholar.org/paper/Approximatio...
Document Type: Working paper
Year of publication: 1999
The title of a journal, publication series: Electronic Colloquium on Computational Complexity : ECCC
Volume: TR99-011
Place of publication: Trier
Publishing house: Universität Trier
ISSN: 1433-8092
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause)
Subject: 004 Computer science, internet
Abstract: 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.
Additional information: Online-Ressource

Dieser Eintrag ist Teil der Universitätsbibliographie.




Metadata export


Citation


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item