A lower bound for integer multiplication on randomized ordered read-once branching programs

摘要

We prove an exponential lower bound 2~(Ω(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 models of randomized branching programs. In contrast, we prove that testing integer multiplication, contrary even to a non-deterministic 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.