A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Farid Mansurovich Ablayev, Marek Karpiński · 1997
We prove an exponential lower bound 2\\Omega\\Gamma 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.