Publication Details
Title: A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Author: F. Ablayev and M. Karpinski
Group: ICSI Technical Reports
Date: December 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-058.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-97-058
Bibliographic Reference:
F. Ablayev and M. Karpinski. A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs. ICSI Technical Report TR-97-058, December 1997
Author: F. Ablayev and M. Karpinski
Group: ICSI Technical Reports
Date: December 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-058.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-97-058
Bibliographic Reference:
F. Ablayev and M. Karpinski. A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs. ICSI Technical Report TR-97-058, December 1997