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⋅Tk=Ω((n/k)k+1).