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

TitleA Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Publication TypeTechnical Report
Year of Publication1997
AuthorsAblayev, F., & Karpinski M.
Other Numbers1120
Abstract

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 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.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1997/tr-97-058.pdf
Bibliographic Notes

ICSI Technical Report TR-97-058

Abbreviated Authors

F. Ablayev and M. Karpinski

ICSI Publication Type

Technical Report