A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Title | A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs |
Publication Type | Technical Report |
Year of Publication | 1997 |
Authors | Ablayev, F., & Karpinski M. |
Other Numbers | 1120 |
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. |
URL | http://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 |