Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-011 | 29th January 1998 00:00

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs



We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the
size of any randomized ordered read-once branching program
computing integer multiplication. Our proof depends on proving
a new lower bound on Yao's randomized one-way communication
complexity of certain boolean functions. It generalizes to some
other common models of randomized branching programs. In contrast,
we prove that testing integer multiplication, contrary even to
nondeterministic situation, can be computed by randomized
ordered read-once branching program in polynomial size. It is also
known that computing the latter problem with deterministic read-once
branching programs is as hard as factoring integers.

ISSN 1433-8092 | Imprint