Randomized OBDDs for the most significant bit of multiplication need exponential space

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Only in 2008 the question whether the deterministic OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. Since probabilistic methods have turned out to be useful in almost all areas of computer science, one may ask whether randomization can help to represent the most significant bit of integer multiplication in smaller size. Here, it is proved that the randomized OBDD complexity is also exponential.

Research highlights
► Randomized OBDDs for the representation of the most significant bit of integer multiplication are investigated.
► For each variable ordering the greater than function is reduced suitably to the most significant bit of integer multiplication.
► The complexity of randomized OBDDs for the most significant bit of multiplication is exponential.