Revision #1 Authors: Ingo Wegener, Philipp Woelfel

Accepted on: 19th March 2005 00:00

Downloads: 3043

Keywords:

In this revision some typos and minor errors of the original report are corrected.

TR04-107 Authors: Ingo Wegener, Philipp Woelfel

Publication: 26th November 2004 17:39

Downloads: 3054

Keywords:

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^(7/4)/log n) and O(n^(7/4)), respectively.