Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR04-107 | 19th March 2005 00:00

New Results on the Complexity of the Middle Bit of Multiplication


Revision #1
Authors: Ingo Wegener, Philipp Woelfel
Accepted on: 19th March 2005 00:00
Downloads: 2975


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


TR04-107 | 24th November 2004 00:00

New Results on the Complexity of the Middle Bit of Multiplication

Authors: Ingo Wegener, Philipp Woelfel
Publication: 26th November 2004 17:39
Downloads: 3007


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.

ISSN 1433-8092 | Imprint