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 ... more >>>