EN|RU Volume 16, No 5, 2009, P. 69-77 UDC 519.714.4 + 519.725 E. A. Okol'nishnikova Lower bound for the computation complexity of BCH-codes for branching programs Abstract: 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, codes. Okolnishnikova Elizaveta Antonovna 1 1. S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia © Sobolev Institute of Mathematics, 2015