  We consider coding schemes for computationally bounded channels, which can
introduce an arbitrary set of errors as long as (a) the fraction of errors is
bounded with high probability by a parameter $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 standard adversarial
errors, they can handle channels whose true behavior is unknown or varying over
time.
  For two classes of channels, we provide explicit, efficiently
encodable/decodable codes of optimal rate where only inefficiently decodable
codes were previously known. In each case, we provide one encoder/decoder that
works for 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.
  (1) Unique decoding for additive errors: We give the first construction of a
polynomial-time encodable/decodable code for additive (a.k.a. oblivious)
channels that achieve the Shannon capacity $1-H(p)$. These channels add an
arbitrary error vector $e\in\{0,1\}^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.
  (2) List-decoding for polynomial-time channels: For every constant $c>0$, we
give a Monte Carlo construction of an code with optimal rate (arbitrarily close
to $1-H(p)$) that efficiently recovers a short list containing the correct
message with high probability for channels describable by circuits of size at
most $N^c$. We justify the relaxation to list-decoding by showing that even
with bounded channels, uniquely decodable codes cannot have positive rate for
$p>1/4$.
