On the OBDD complexity of the most significant bit of integer multiplication (Q2430011)

OBDDs are decision diagrams (also called branching programs) for Boolean functions where each variable may only be read at most once and there is a fixed ordering on the variables. They are a state-of-the-art data structure for Boolean functions. The size of an OBDD depends on the variable ordering. For a Boolean function, its OBBD size is the minimum size of an OBDD for it, where the minimum is taken over all variable orderings. While many important functions have OBDDs of small size, there are also important functions with large OBDD sizes. For the middle bit of integer multiplication it is long known that the OBDD size is exponential [\textit{R. E. Bryant}, IEEE Trans. Comput. 40, No.~2, 205--213 (1991; Zbl 1220.68060)]. This paper establishes an exponential lower bound for the most signification bit. A lower bound of \(\Omega(2^{n/288})\) is proved. For the natural interleaving variable ordering an improved lower bound of \(\Omega(2^{n/4})\) is shown. The proofs are based on communication complexity.