| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429254 | Information Processing Letters | 2006 | 4 Pages |
Abstract
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).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
