Geodesic
Lower bound for the computation complexity of BCH-codes for branching programs
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 69-77.

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

A lower bound $\Omega(n\log n)$ for the computation complexity of characteristic functions of Bose–Chaudhuri–Hoquinghem codes (BCH-codes) for some values of parameters of these codes by nondeterministic branching programs is obtained. Bibl. 9.
Keywords: complexity, lower bound, branching program
Mots-clés : codes. 
@article{DA_2009_16_5_a6,
     author = {E. A. Okolnishnikova},
     title = {Lower bound for the computation complexity of {BCH-codes} for branching programs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {69--77},
     publisher = {mathdoc},
     volume = {16},
     number = {5},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_5_a6/}
}
TY  - JOUR
AU  - E. A. Okolnishnikova
TI  - Lower bound for the computation complexity of BCH-codes for branching programs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 69
EP  - 77
VL  - 16
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_5_a6/
LA  - ru
ID  - DA_2009_16_5_a6
ER  - 
%0 Journal Article
%A E. A. Okolnishnikova
%T Lower bound for the computation complexity of BCH-codes for branching programs
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 69-77
%V 16
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_5_a6/
%G ru
%F DA_2009_16_5_a6
E. A. Okolnishnikova. Lower bound for the computation complexity of BCH-codes for branching programs. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 69-77. http://geodesic.mathdoc.fr/item/DA_2009_16_5_a6/

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

[2] 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–102 | MR | Zbl

[3] Okolnishnikova E. A., “O slozhnosti nedeterminirovannykh vetvyaschikhsya programm, realizuyuschikh kharakteristicheskie funktsii kodov Rida–Mallera”, Diskret. analiz i issled. operatsii. Ser. 1, 10:3 (2003), 67–81 | MR

[4] Razborov A. A., “Nizhnie otsenki slozhnosti realizatsii simmetricheskikh bulevykh funktsii kontaktno–ventilnymi skhemami”, Mat. zametki, 48:6 (1990), 79–90 | MR | Zbl

[5] Ajtai M., “A non-linear time lower bound for boolean branching programs”, Proc. of the 40th annual Symp. on foundations of Comp. Sci., FOCS' 99 (New York, October 17–19, 1999), IEEE Comp. Soc., Los Alamitos, 1999, 60–70 | MR

[6] Babai L., Pudlák P., Rödl V., Szemerédi M., “Lower bounds to the complexity of symmetric Boolean functions”, Theoret. Comput. Sci., 74:3 (1990), 313–324 | DOI | MR

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

[8] Pudlák P., “The hierarchy of Boolean circuits”, Computers and Artificial Intelligence, 6:5 (1987), 449–468 | MR | Zbl

[9] Thathachar J. S., “On separating the read-$k$-times program hierarchy”, Proc. of the 30th Ann. ACM Symp. on Theory of Computing, STOC' 98 (Dallas, May 23–26, 1998), ACM, New York, 1999, 653–662 | MR