𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On random orderings of variables for parity ordered binary decision diagrams

✍ Scribed by Petr Savický

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
93 KB
Volume
16
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

Ordered binary decision diagrams (OBDDs) are a model for representing

Boolean functions. There is also a more powerful variant called parity OBDDs. The size of the representation of a given function depends in both these models on the chosen ordering of the variables. It is known that there are functions such that almost all orderings of their variables yield an OBDD of polynomial size, but there are also some exceptional orderings, for which the size is exponential. We prove that for parity OBDDs, the size for a random ordering and the size for the worst ordering are polynomially related. More exactly, for every ε > 0 there is a number c > 0 such that the following holds. If a Boolean function f of n variables is such that a random ordering of the variables yields a parity OBDD for f of size at most s with probability at least ε, where s ≥ n, then every ordering of the variables yields a parity OBDD for f of size at most s c .

📜 SIMILAR VOLUMES

On Stochastic Orders for Sums of Indepen
On Stochastic Orders for Sums of Independent Random Variables
✍ Ramesh M. Korwar 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 131 KB

In this paper, it is shown that a convolution of uniform distributions (a) is more dispersed and (b) has a smaller hazard rate when the scale parameters of the uniform distributions are more dispersed in the sense of majorization. It is also shown that a convolution of gamma distributions with a com

Stochastic Orders for Spacings of Hetero
Stochastic Orders for Spacings of Heterogeneous Exponential Random Variables
✍ Subhash C Kochar; Ramesh Korwar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 489 KB

We obtain some new results on normalized spacings of independent exponential random variables with possibly different scale parameters. It is shown that the density functions of the individual normalized spacings in this case are mixtures of exponential distributions and, as a result, they are log-c

Very weak zero one law for random graphs
Very weak zero one law for random graphs with order and random binary functions
✍ Saharon Shelah 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 450 KB 👁 1 views

Natural languages and random structures are given for which there are sentences A with no limit probability, yet for every A the difference between the probabilities that A holds on random structures of sizes n and n + 1 approaches zero with n.

Variable orderings and the size of OBDDs
Variable orderings and the size of OBDDs for random partially symmetric Boolean functions
✍ Detlef Sieling 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB 👁 3 views

The size of ordered binary decision diagrams OBDDs strongly depends on the chosen variable ordering. It is an obvious heuristic to use symmetric variable orderings, i.e., variable orderings where symmetric variables are arranged adjacently. In order to evaluate this heuristic, methods for estimating

Lower convex order bound approximations
Lower convex order bound approximations for sums of log-skew normal random variables
✍ Oriol Roch; Emiliano A. Valdez 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB

When it comes to modeling dependent random variables, not surprisingly, the multivariate normal distribution has received the most attention because of its many appealing properties. However, when it comes to practical implementation, the same family of distribution is often rejected for modeling fi