A note on the decoding complexity of error-correcting codes
A time-space tradeoff lower bound for the decoding complexity of asymptotically good error-correcting codes for oblivious write-k-times branching programs is proved. Specifically, we prove that the computation time T and space S of every oblivious write-k-times branching program that decodes an asymptotically good error-correcting code with block length n satisfy S (.) T-k = Omega((n/k)(k+1)). (c) 2006 Elsevier B.V. All rights reserved.
error-correcting codes branching programs computational complexity