STOC2021
Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity
Ronen Shaltiel, Jad Silbak
1 citation
Abstract
We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a p fraction of the bits of the codeword.