Geodesic
On the Complexity of Randomized Read-once Branching Programs
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 107-113

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

Ordered binary decision diagrams are a well known computational model. Graph-driven read-once branching programs presented in this paper generalize this model. Exponential lower bound of the complexity of such programs for integer multiplication is proven.
Keywords: Boolean function, binary branching program, complexity class, computation complexity lower bound. 
@article{UZKU_2009_151_2_a12,
     author = {R. G. Mubarakzjanov},
     title = {On the {Complexity} of {Randomized} {Read-once} {Branching} {Programs}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {107--113},
     publisher = {mathdoc},
     volume = {151},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a12/}
}
TY  - JOUR
AU  - R. G. Mubarakzjanov
TI  - On the Complexity of Randomized Read-once Branching Programs
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2009
SP  - 107
EP  - 113
VL  - 151
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a12/
LA  - ru
ID  - UZKU_2009_151_2_a12
ER  - 
%0 Journal Article
%A R. G. Mubarakzjanov
%T On the Complexity of Randomized Read-once Branching Programs
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2009
%P 107-113
%V 151
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a12/
%G ru
%F UZKU_2009_151_2_a12
R. G. Mubarakzjanov. On the Complexity of Randomized Read-once Branching Programs. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 107-113. http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a12/