Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOM ORDERING OF VARIABLES:
Reports tagged with random ordering of variables:
TR98-068 | 12th November 1998
Petr Savicky

On Random Orderings of Variables for Parity OBDDs

There are Boolean functions such that almost all orderings of
its 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
... more >>>




ISSN 1433-8092 | Imprint