Report TR04-107.
Abstract. It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}. This paper contains several new results on its complexity. First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated. A randomized algorithm for MUL_{n-1,n} with k=O(log n) (implying time O(n*log n)), space O(log n) and error probability 1/n^c for arbitrarily chosen constants c is presented. This is close to the known deterministic lower bound for the space requirement in the order of n*2^(-O(k)). Second, the size of general branching programs and formulas is investigated. Applying Nechiporuk's technique, lower bounds of Omega(n^(3/2)/log n) and Omega(n^(3/2)), respectively, are obtained. Moreover, by bounding the number of subfunctions of MUL_{n-1,n}, it is proven that Nechiporuk's technique cannot provide larger lower bounds than O(n^(5/3)/log n) and O(n^(5/3)), respectively.