This article is cited in 3 papers

Lower bound for the computation complexity of BCH-codes for branching programs

E. A. Okolnishnikova

S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

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.

UDC: 519.714.4+519.725

Received: 10.08.2009

 English version: Journal of Applied and Industrial Mathematics, 2010, 4:2, 231–235

Bibliographic databases:

• 
• 
•