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
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.
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