Seminar Room, Room 261, Ziskind Building
                          on Monday, December 20, 2010
                                    at 14:30

                              Venkatesan Guruswami
                           Carnegie Mellon University

                                 will speak on


                         Bridging Shannon and Hamming:
                   Codes for computationally simple channels

Abstract:
The theory of error-correcting codes has had two divergent schools of thought,
dating back to its origins, based on the underlying model of the noisy
channel.  Shannon's theory modeled the channel as a stochastic process with a
known probability law. Hamming's work suggested a worst-case model, where the
channel is subject only to a limit on the number of errors it may cause. These
two approaches share several common tools, however in terms of quantitative
results, the classical results in the harsher Hamming model are much weaker.
For example, when transmitting bits, error recovery from more than a fraction
1/4 of worst-case errors is not possible, whereas even close to a fraction 1/2
of random errors can be corrected.

In this talk, we will discuss a line of research aimed at bridging between
these models. We will begin by surveying some approaches that rely on setup
assumptions (such as shared randomness) to construct codes against worst-case
errors with efficiency similar to what is possible against random errors. We
then turn to our results for computationally bounded channels, which can
introduce an arbitrary set of errors as long as (a) the total fraction of
errors is bounded by a parameter p, and (b) the process which adds the errors
is sufficiently ``simple'' computationally. Such channel models are
well-motivated as physical noise processes may be mercurial, but are not
computationally intensive. Also, as with codes for worst-case errors, codes for
such channels can handle errors whose true behavior is unknown or varying over
time.

We will describe an explicit construction of a poly-time encodable/decodable
code of rate approaching Shannon capacity 1-h(p) that can correct an arbitrary
error pattern with total fraction of errors bounded by p, provided the
channel's action is oblivious to the codeword. We will hint at an extension to
channels limited to online logarithmic space that gives efficient codes with
optimal rate that enable recovery of a short list containing the correct
message.  (A similar claim holds for channels admitting polynomial size
circuits, assuming the existence of pseudorandom generators.) Our results do
not use any shared randomness or other setup assumptions.

Based on joint work with Adam Smith.