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

We prove an exponential lower bound 2Ω(n/logn) 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 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.

Authors

• Farid Ablayev
• Marek Karpinski

Keywords

• Deterministic and randomized branching programs
• OBDD
• Complexity
• Lower bounds
• Integer multiplication
• Randomized algorithms