Size and structure of random ordered binary decision diagrams
C Gröpl, HJ Prömel, A Srivastav - Annual Symposium on Theoretical …, 1998 - Springer
C Gröpl, HJ Prömel, A Srivastav
Annual Symposium on Theoretical Aspects of Computer Science, 1998•SpringerWe investigate the size and structure of ordered binary decision diagrams (OBDDs) for
random Boolean functions. Wegener [Weg94] proved that for “most” values of n, the
expected OBDD-size of a random Boolean function with n variables equals the worst-case
size up to terms of lower order. Our main result is that this phenomenon, also known as
strong Shannon effect, shows a threshold behaviour: The strong Shannon effect does not
hold within intervals of constant width around the values n= 2 h+ h, but it does hold outside …
random Boolean functions. Wegener [Weg94] proved that for “most” values of n, the
expected OBDD-size of a random Boolean function with n variables equals the worst-case
size up to terms of lower order. Our main result is that this phenomenon, also known as
strong Shannon effect, shows a threshold behaviour: The strong Shannon effect does not
hold within intervals of constant width around the values n= 2 h+ h, but it does hold outside …
Abstract
We investigate the size and structure of ordered binary decision diagrams (OBDDs) for random Boolean functions. Wegener [Weg94] proved that for “most” values of n, the expected OBDD-size of a random Boolean function with n variables equals the worst-case size up to terms of lower order. Our main result is that this phenomenon, also known as strong Shannon effect, shows a threshold behaviour: The strong Shannon effect does not hold within intervals of constant width around the values n = 2h + h, but it does hold outside these intervals. Also, the oscillation of the expected and the worst-case size is described. Methodical innovations of our approach are a functional equation to locate “critical levels” in OBDDs and the use of Azuma's martingale inequality and Chvátal's large deviation inequality for the hypergeometric distribution. This leads to significant improvements over Wegener's probability bounds.
Springer
Showing the best result for this search. See all results