Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with time-space product:
TR04-107 | 24th November 2004
Ingo Wegener, Philipp Woelfel

New Results on the Complexity of the Middle Bit of Multiplication

Revisions: 1

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

ISSN 1433-8092 | Imprint