Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-068 | 12th November 1998 00:00

On Random Orderings of Variables for Parity OBDDs

RSS-Feed




TR98-068
Authors: Petr Savicky
Publication: 7th December 1998 12:10
Downloads: 1964
Keywords: 


Abstract:

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
and the size for the worst ordering are polynomially related.

More exactly, for every \epsilon>0 there is a number c>0 such
that the following holds. If a Boolean function f is such that
a random ordering of the variables yields a parity OBDD
for f of size at most s with probability at least \epsilon,
then every ordering of the variables yields a parity OBDD for f
of size at most s^c.



ISSN 1433-8092 | Imprint