TR98-011 Authors: Farid Ablayev, Marek Karpinski

Publication: 18th February 1998 12:22

Downloads: 1899

Keywords:

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.