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