ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 68, 05C80 Gröpl, Clemens, Humboldt-Universität zu Berlin, Germany Random OBDDs The Ordered Binary Decision Diagram is a graph-based representation of Boolean functions (very roughly, a decision tree in which isomorphic parts have been identified). OBDDs accommodate many basic operations within polynomial space and time and have been applied successfully in many areas. Our interest is theoretical: We investigate the size of OBDDs for random Boolean functions. It turns out that for most values of n := #variables, a random OBDD has almost the largest possible size with high probability, but some strange things happen near n = 2^{h} + h. Our probabilistic tools are urn experiments and large deviation inequalities. Reference: Size and Structure of Random Ordered Binary Decision Diagrams, C. Gröpl, H. J. Prömel, A. Srivastav, Proc. 15th Ann. Symp. on Theor. Asp. of Comp. Science, Paris, 1998, Springer LNCS 1373, pp. 238–