ECCC-Report TR98-011https://eccc.weizmann.ac.il/report/1998/011Comments and Revisions published for TR98-011en-usWed, 18 Feb 1998 12:22:53 +0200
Paper TR98-011
| A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs |
Farid Ablayev,
Marek Karpinski
https://eccc.weizmann.ac.il/report/1998/011We prove an exponential lower bound ($2^{\Omega(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.
Wed, 18 Feb 1998 12:22:53 +0200https://eccc.weizmann.ac.il/report/1998/011