A lower bound on the computation complexity of characteristic functions for BCH-codes by branching programs
Elizaveta A. Okol’nishnikova · Journal of Applied and Industrial Mathematics · 2010
We give the lower bound Ω( n log n ) on the complexity of nondeterministic branching programs computing the characteristic functions of Bose-Chaudhuri-Hocquenghemcodes (BCH-codes) for some values of parameters of these codes.