Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V
85184

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Farid Ablayev, Marek Karpinski
[Download PostScript] [Download PDF]

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the size of any {\em randomized} ordered read-once branching program computing {\em 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 {\em testing integer multiplication}, contrary even to nondeterministic situation, can be computed by {\em 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.

Last Change: 07/05/01 at 14:13:36
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope