Ordered binary decision diagrams and the Shannon effect
type: Item
instance of: scholarly article
title: Ordered binary decision diagrams and the Shannon effect
zbMATH Open document ID: 1062.94075
author: Clemens Gröpl
author: Hans Jürgen Prömel
author: Anand Srivastav
published in: Discrete Applied Mathematics
publication date: 2004-08-19T00:00:00Z
review text: The state-of-the-art data structures for Boolean functions are known as ordered binary decision diagrams (OBDDs). An OBDD is an acyclic digraph with one root and two terminals 0 and 1. This paper is devoted to theoretical investigations on the size of the OBDD of a Boolean function which has been chosen according to the uniform distribution. Using counting arguments, \textit{H. Liaw} and \textit{C. Lin} [IEEE Trans. Comput. 41, 661--664 (1992)] showed that the expected optimal OBDD size in this model is never more than a constant factor apart from the worst-case OBDD size of any function on \(n\) variables. Later \textit{I. Wegener} [IEEE Trans. Comput. 43, 1262--1269 (1994; Zbl 1068.68685)] showed that the two quantities in fact coincide up to terms of lower order, if the number of variables is uniformly distributed in \([2^{h},2^{h+1}-1]\) and \(h\) goes to infinity. The phenomenon that almost all functions have the same OBDD size as the hardest functions up to a factor of \(1+o(1)\) is called the strong Shannon effect for random Boolean functions and OBDDs. The authors show that the strong Shannon effect is not valid for all \(n\). More precisely, the strong Shannon effect does not hold within intervals of constant width around the values \(n=2^{h}+h\), where \(h\) is a natural number, but it does hold outside these intervals. Their analysis uses a large deviation inequality that follows from Azuma's martingale inequality, and Chvátal's bound on the hypergeometric distribution. This new approach proposes a generalization of OBDDs called ordered Kronecker functional decision diagrams (OKFDDs).
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 2093409
zbMATH Keywords: binary decision diagram
zbMATH Keywords: random Boolean function
zbMATH Keywords: probabilistic analysis
zbMATH Keywords: Shannon effect
reviewed by: Ioan Tomescu
describes a project that uses: CUDD
MaRDI profile type: Publication
full work available at URL: j.dam.2003.02.003
OpenAlex ID: W2031729686
cites work: OKFDDs versus OBDDs and OFDDs
cites work: On the relation between BDDs and FDDs
cites work: On the size of binary decision diagrams representing Boolean functions
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
cites work: The tail of the hypergeometric distribution
cites work: Two-level logic minimization: an overview
cites work: Fast OFDD-based minimization of fixed polarity Reed-Muller expressions
cites work: Balls and bins: A study in negative dependence
cites work: On the evolution of the worst-case OBDD size
cites work: Least upper bounds on OBDD sizes
cites work: Tail bounds for occupancy and the satisfiability threshold conjecture
cites work: On the OBDD-representation of general Boolean functions
cites work: Q4864698
cites work: Q4219538
cites work: The nonapproximability of OBDD minimization
cites work: The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
DOI: 10.1016/J.DAM.2003.02.003
description: scientific article; zbMATH DE number 2093409