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.