Geodesic
On the complexity of nondeterministic branching programs that realize characteristic functions of Reed--Muller codes
Diskretnyj analiz i issledovanie operacij, Tome 10 (2003) no. 3, pp. 67-81.

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

@article{DA_2003_10_3_a4,
     author = {E. A. Okolnishnikova},
     title = {On the complexity of nondeterministic branching programs that realize characteristic functions of {Reed--Muller} codes},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {67--81},
     publisher = {mathdoc},
     volume = {10},
     number = {3},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2003_10_3_a4/}
}
TY  - JOUR
AU  - E. A. Okolnishnikova
TI  - On the complexity of nondeterministic branching programs that realize characteristic functions of Reed--Muller codes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2003
SP  - 67
EP  - 81
VL  - 10
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2003_10_3_a4/
LA  - ru
ID  - DA_2003_10_3_a4
ER  - 
%0 Journal Article
%A E. A. Okolnishnikova
%T On the complexity of nondeterministic branching programs that realize characteristic functions of Reed--Muller codes
%J Diskretnyj analiz i issledovanie operacij
%D 2003
%P 67-81
%V 10
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2003_10_3_a4/
%G ru
%F DA_2003_10_3_a4
E. A. Okolnishnikova. On the complexity of nondeterministic branching programs that realize characteristic functions of Reed--Muller codes. Diskretnyj analiz i issledovanie operacij, Tome 10 (2003) no. 3, pp. 67-81. http://geodesic.mathdoc.fr/item/DA_2003_10_3_a4/

[1] Mak-Vilyams F. Dzh., Sloen N. Dzh. A., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[2] Okolnishnikova E. A., “Nizhnie otsenki slozhnosti realizatsii kharakteristicheskikh funktsii dvoichnykh kodov binarnymi programmami”, Metody diskretnogo analiza v sinteze realizatsii bulevykh funktsii, Sb. nauch. tr., no. 51, In-t matematiki SO AN SSSR, Novosibirsk, 1991, 61–83 | MR

[3] Okolnishnikova E. A., “Slozhnost vetvyaschikhsya programm”, Matematicheskie voprosy kibernetiki, no. 10, Fizmatlit, M., 2001, 69–82 | MR

[4] Okolnishnikova E. A., “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti realizatsii bulevykh funktsii nedeterminirovannymi vetvyaschimisya programmami”, Diskret. analiz i issled. operatsii. Ser. 1, 8:4 (2001), 76–112 | MR

[5] Borodin A., Razborov A., Smolensky R., “On lower bounds for read-$k$-times branching programs”, Computational Complexity, 3:1 (1993), 1–18 | DOI | MR | Zbl

[6] Okol'nishnikova E. A., “On the hierarchy of nondeterministic branching $k$-programs”, Fundamentals of computation theory, 11th International symposium, FCT 97, Lecture Notes in Comput. Sci., 1279, Springer, Berlin, 1997, 376–387 | MR

[7] Razborov A. A., “Lower bounds for deterministic and nondeterministic branching program”, Fundamentals of computation theory, Proc. 8th International symposium, FCT 91 (Gosen, Germany, September 9–13, 1991), Lecture Notes in Comput. Sci., 529, Springer, Berlin, 1991, 47–61 | MR

[8] Thathachar J. S., “On separating the read-$k$-times program hierarchy”, Proc. of the 30th annual ACM Symposium on theory of comptuting (Dallas, 1998), ACM Press, New York, 1998, 652–662

[9] Wei V. K., “Generalized Hamming weights for linear codes”, IEEE Trans. on Inform. Theory, 37:5 (1991), 1412–1418 | DOI | MR | Zbl