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. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia