A note on the decoding complexity of error-correcting codes

DOI10.1016/j.ipl.2006.06.006zbMath1189.94057OpenAlexW2064548203MaRDI QIDQ845843

André Gronemeier

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.06.006

zbMATH Keywords

computational complexitybranching programserror-correcting codes

Mathematics Subject Classification ID

Decoding (94B35) Theory of computing (68Q99) Synchronization error-correcting codes (94B50)

Related Items (1)

Bounded Independence Plus Noise Fools Products

Cites Work

• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
• A time-space tradeoff for sorting on non-oblivious machines
• The computational complexity of universal hashing
• Time-space tradeoffs for branching programs
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• Time-space trade-off lower bounds for randomized computation of decision problems
• Endcoding Complexity Versus Minimum Distance
• Branching Programs and Binary Decision Diagrams

This page was built for publication: A note on the decoding complexity of error-correcting codes