Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


In this paper, we consider coding schemes for emph{computationally bounded} channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded by $p$ w.h.p. and (b) the process which adds the errors can be described by a sufficiently ``simple'' circuit. Codes for such channel models are attractive since, like codes for traditional adversarial errors, they can handle channels whose true behavior is emph{unknown} or emph{varying} over time.

For three classes of channels, we provide explicit, efficiently encodable/decodable codes of optimal rate where only emph{in}efficiently decodable codes were previously known. In each case, we provide one encoder/decoder that works for emph{every} channel in the class. The encoders are randomized, and probabilities are taken over the (local, unknown to the decoder) coins of the encoder and those of the channel.

Unique decoding for additive errors: We give the first construction of polytime encodable/decodable codes for emph{additive} (a.k.a. emph{oblivious}) channels that achieve the Shannon capacity $1-H(p)$. These are channels which add an arbitrary error vector $einit{n}$ of weight at most $pn$ to the transmitted word; the vector $e$ can depend on the code but not on the particular transmitted word. Such channels capture binary symmetric errors and burst errors as special cases.

List-decoding for log-space channels: A emph{space-$S(n)$ bounded} channel reads and modifies the transmitted codeword as a stream, using at most $S(n)$ bits of workspace on transmissions of $n$ bits. For constant $S$, this captures many models from the literature, including emph{discrete channels with finite memory} and emph{arbitrarily varying channels}. We give an efficient code with optimal rate (up to $1-H(p)$) that recovers a short list containing the correct message with high probability for channels limited to emph{logarithmic} space.

List-decoding for poly-time channels: For any const

Questions and Answers

You need to be logged in to be able to post here.