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

A Lower Bound for Integer Multiplication on Randomized ReadOnce 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 readonce branching program computing {\em integer multiplication}. Our proof depends on proving a new lower bound on Yao's randomized oneway 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 readonce branching program in polynomial size. It is also known that computing the latter problem with deterministic readonce 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 