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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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},
     year = {2009},
     volume = {151},
     number = {2},
     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
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
%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/

[1] Wegener I., Branching Programs and Binary Decision Diagrams: Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications, Soc. Ind. Appl. Math., Philadelphia, USA, 2000, 408 pp. | MR | Zbl

[2] Ablayev F., Karpinski M., “On the power of randomized ordered branching programs”, Proc. ICALP' 96, Lecture Notes Comput. Sci., 1099, Springer, 1996, 348–356 | DOI | MR | Zbl

[3] Ablayev F., Karpinski M., Mubarakzjanov R., “On $BPP$ versus $NP\cup coNP$ for Ordered Read-Once Branching Programs”, Theoret. Comp. Sci., 264 (2001), 127–137 | DOI | MR | Zbl

[4] Ablayev F., “Randomization and nondeterminism are incomparable for ordered read-once branching programs”, Proc. ICALP' 97, Lecture Notes Comput. Sci., 1256, Springer, 1997, 195–202 | DOI | MR

[5] Ablayev F., Karpinski M., A lower bound for integer multiplication on randomized read-once branching programs, Electronical Colloquium on Computational Complexity: ECCC TR98-011, Trier University, Trier, 1998 ; http://www.eccc.uni-trier.de/ECCC/ | Zbl

[6] Mubarakzyanov R. G., “Nizhnie otsenki slozhnosti veroyatnostnykh binarnykh programm s bolshoi uporyadochennoi chastyu”, Izv. vuzov. Matem., 2006, no. 6, 56–64 | MR | Zbl

[7] Gergov J., Meinel C., “Efficient Boolean manipulation with $OBDD$s can be extended to $FBDD$s”, IEEE Trans. on Computers, 43 (1994), 1197–1209 | DOI | Zbl

[8] Sieling D., Wegener I., “Graph driven BDDs – a new data structure for Boolean functions”, Theoret. Comp. Sci., 141 (1995), 283–310 | DOI | MR | Zbl

[9] Bollig B., “Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication”, RAIRO Theoretical Informatics and Applications, 35 (2001), 149–162 | DOI | MR | Zbl

[10] Bollig B., Woelfel Ph., “A lower bound technique for nondeterministic graph-driven read-once branching programs and its applications”, Proc. of MFCS, Lecture Notes Comput. Sci., 2420, Springer, 2002, 131–142 | DOI | MR | Zbl

[11] Bollig B., Waack S., Woelfel Ph., “Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication”, Proc. of IFIP 2nd Int. Conf. on Theoretical Computer Science, 2002, 83–94

[12] Chernoff H., “A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations”, Ann. Math. Stat., 23 (1952), 493–509 | DOI | MR