New results on the complexity of the middle bit of multiplication

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 n^-c for arbitrarily chosen constants c is presented. Second, the size of general branching programs and formulas is investigated. Applying Nechiporuk´s technique, lower bounds of Ω(n³2//log n) and Ω(n³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⁷4//log n) and O(n⁷4/), respectively.