[crypto] [Ronald.Cramer at cwi.nl: [risc-list] RISC at CWI Fri Nov 25: Venkat Guruswami]

[R. Hirschfeld]

------- Start of forwarded message -------
Date: Mon, 14 Nov 2011 12:34:23 +0100 (CET)
From: Ronald Cramer <Ronald.Cramer at cwi.nl>
Subject: [risc-list] RISC at CWI Fri Nov 25: Venkat Guruswami

Dear Colleagues,

it's our pleasure to invite you to a RISC seminar talk on 

  ``Bridging Shannon and Hamming: Codes for computationally simple channels''

                            by 

               Prof Venkatesan Guruswami (Carnegie Mellon U) 


It will be held at CWI on
   
             *Friday Nov 25, 1600h-1700h (Room L017)* 


The abstract is quoted at the end of this message and can also be found on the 
RISC website http://www.cwi.nl/crypto/risc.html

This talk in our RISC seminar is organized in collaboration with the CWI groups Algorithms, Combinatorics and Optimization (PNA1) and Algorithms & Complexity (PNA6)


See you then and there!


best regards, Ronald Cramer and Serge Fehr 
(also on behalf of Monique Laurent (PNA1) and Harry Buhrman (PNA6))


http://www.cwi.nl/crypto/
http://www.cwi.nl/crypto/risc.html


======================================================
Abstract of Prof Guruswami's talk:

Coding theory 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.

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 information rate 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
since 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 polynomial time
encodable/decodable codes with 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.
========================================================




_______________________________________________
risc-list mailing list
risc-list at cwi.nl
https://lists.cwi.nl/mailman/listinfo/risc-list
------- End of forwarded message -------