Geodesic
Lower bounds for the complexity of probabilistic binary programs with a large ordered part
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2006), pp. 56-64.

Voir la notice de l'article provenant de la source Math-Net.Ru

@article{IVM_2006_6_a5,
     author = {R. G. Mubarakzyanov},
     title = {Lower bounds for the complexity of probabilistic binary programs with a large ordered part},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {56--64},
     publisher = {mathdoc},
     number = {6},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2006_6_a5/}
}
TY  - JOUR
AU  - R. G. Mubarakzyanov
TI  - Lower bounds for the complexity of probabilistic binary programs with a large ordered part
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2006
SP  - 56
EP  - 64
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2006_6_a5/
LA  - ru
ID  - IVM_2006_6_a5
ER  - 
%0 Journal Article
%A R. G. Mubarakzyanov
%T Lower bounds for the complexity of probabilistic binary programs with a large ordered part
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2006
%P 56-64
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2006_6_a5/
%G ru
%F IVM_2006_6_a5
R. G. Mubarakzyanov. Lower bounds for the complexity of probabilistic binary programs with a large ordered part. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2006), pp. 56-64. http://geodesic.mathdoc.fr/item/IVM_2006_6_a5/

[1] Wegener I., Branching programs and binary desicion diagrams: theory and applications, SIAM Monographs on Discrete Math. and Appl., Philadelphia, USA, 2000, 408 pp. | MR

[2] Ablayev F., Karpinski M., Mubarakzjanov R., “On $BPP$ versus $NP\cup coNP$ for ordered read-once branching programs”, Theoret. Comput. Sci., 264 (2001), 127–137 | DOI | MR | Zbl

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

[4] Ablayev F., Karpinski M., “A lower bound for integer multiplication on randomized read-once branching programs”, Electron. Colloq. on Comput. Compl., Trier University, Trier, 1998 ; ECCC TR98–011 http://www.eccc.uni-trier.de/ECCC | Zbl

[5] Sauerhoff M., “Lower bounds for randomized read-$k$-times branching programs”, Proc. STACS'98, LNCS, 1373, Springer, 1998, 105–115 | MR

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

[7] Gergov J., Meinel C., “Efficient Boolean manipulation with OBDDs can be extended to FBDDs”, IEEE Transac. Comput., 43:10 (1994), 1197–1209 | DOI | Zbl

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

[9] Jukna S., “Entropy of contact circuits and lower bounds on their complexity”, Theoret. Comput. Sci., 57 (1988), 113–129 | DOI | MR | Zbl

[10] Jukna S., Razborov A., Savicky P., Wegener I., “On $P$ versus $NP\cap co$-$NP$ for decision trees and read-once branching programs”, Comput. Compl., 8 (1999), 357–370 | DOI | MR | Zbl

[11] Bryant R. E., “On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication”, IEEE Trans. Comput., C-40:2 (1991), 205–213 | DOI | MR

[12] Breitbard Y., Hunt III H. B., Rosenkratz D., “On the size of binary decision diagrams representing Boolean functions”, Theoret. Comput. Sci., 145 (1995), 45–69 | DOI | MR

[13] Ponzio S., “A lower bound for integer multiplication with read-once branching programs”, Proc. 27-th STOC, 1995, 130–139 | Zbl

[14] Karpinski M., Mubarakzjanov R., “Some separation problems on randomized OBDDs”, Proc. of the International Workshop on Computer Science and Information Technologies, CSIT'99 (Moscow, Russia), 1999, http://msu.jurinfor.ru/CSIT99/

[15] Savicky P., Zak S., “A hierarchy for $(1, +k)$-branching programs with respect to $k$”, Proc. MFCS'97, LNCS, 1295, 1997, 478–487 | MR | Zbl

[16] Dias J. A., Hamidoune Y. O., “Cyclic spaces for Grassmann derivatives and additive theory”, Bull. London Math. Soc., 26 (1994), 140–146 | DOI | MR | Zbl

[17] Bollig B., Sauerhoff M., Sieling D., Wegener I., “On the power of different types of restricted branching programs”, Electron. Colloq. on Comput. Compl., Trier University, Trier, 1994; ECCC TR94–026 http://www.eccc.uni-trier.de/ECCC

[18] Mubarakzjanov R., “On probabilistic OBDDs with constant width”, Proc. of the 2nd International Workshop on Computer Science and Information Technologies, CSIT'2000. V. 2 (Ufa, Russia), USATU Publisher, Ufa, 2000, 62–68

[19] 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