ECCC-Report TR04-107https://eccc.weizmann.ac.il/report/2004/107Comments and Revisions published for TR04-107en-usSat, 19 Mar 2005 00:00:00 +0200
Revision 1
| New Results on the Complexity of the Middle Bit of Multiplication |
Ingo Wegener,
Philipp Woelfel
https://eccc.weizmann.ac.il/report/2004/107#revision1In this revision some typos and minor errors of the original report are corrected.
Sat, 19 Mar 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2004/107#revision1
Paper TR04-107
| New Results on the Complexity of the Middle Bit of Multiplication |
Ingo Wegener,
Philipp Woelfel
https://eccc.weizmann.ac.il/report/2004/107It 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.
Fri, 26 Nov 2004 17:39:01 +0200https://eccc.weizmann.ac.il/report/2004/107