WPI Cryptography Seminar on Thursday, April 10

R. A. Hettinga rah at shipwright.com
Wed Apr 9 16:59:42 EDT 2003

--- begin forwarded text

Date: Tue, 8 Apr 2003 19:37:10 -0400
To: undisclosed-recipient:;
From: Monty Solomon <monty at roscom.com>
Subject: WPI Cryptography Seminar on Thursday, April 10

Date: Tue, 8 Apr 2003 08:35:43 -0400 (EDT)
From: Berk Sunar <sunar at hutt.ece.wpi.edu>
Subject: WPI Cryptography Seminar on Thursday, April 10

                       WPI Cryptography Seminar

              List Decoding of Error Correcting Codes


                        Prof. Madhu Sudan

              Massachusetts Institute of Technology
                         Cambridge, MA

                 DATE:  Thursday, April 10, 2003
                 TIME:  4:00 PM
                PLACE:  Stratton Hall, WPI, Room 203


 The task of dealing with errors (or correcting them) lies at the very
 heart of communication and computation. The mathematical foundations for
 this task were laid in two concurrent and interdependent works by Shannon
 and Hamming in the late 1940s. The two theories are strikingly powerful
 and distinct in their modelling of the error. Shannon's theory models
 errors as effected by a probabilistic/stochastic process, while Hamming
 envisions them as being introduced by an adversary. While the two
 theories share a lot in the underlying tools, the quantitative results
 are sharply diverging. Shannon's theory shows that a channel that corrupt
 (arbitrarily) close to 50% of the transmitted bits can still be used for
 transmission of information. Hamming's theory in contrast has often been
 interpreted to suggest it can handle at most 25% error on a binary

 So what can we do if an adversary is given the power to introduce more
 than 25% errors? Can we protect information against this, or do we just
 have to give up?  The notion of list-decoding addresses precisely this
 question, and shows that under a relaxed notion of "decoding" (or
 recovering from errors), the quantitative gaps between the Shannon and
 Hamming theories can be bridged. In this talk, we will describe this
 notion and some recent algorithmic developments. If time permits we will
 show how this notion lies at the heart of many issues in modern
 complexity theory and the foundations of cryptography.


 This WPI Cryptoseminar is being held in the Stratton Hall building on
 the WPI campus. Directions to the campus can be found at



 The seminar is open to everyone and free of charge. Simply send me a
 brief email if you plan to attend.


 If you want to be added to the mailing list and receive talk
 announcements together with abstracts, please send us a short
 e-mail message.

 On the other hand, if you want to be removed from the list,
 just send a reply to this message with the word "remove" in the
 subject line.

 Abstracts of previous and upcoming seminars can be found at



 Berk Sunar and Bill Martin


  Berk Sunar,                             Assistant Professor
  Electrical & Computer Eng. Dept.         Ph (508) 831 54 94
  Worcester Polytechnic Institute          Fx (508) 831 54 91
  http://ece.wpi.edu/research/crypt/          CRIS Laboratory

--- end forwarded text

R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com

More information about the cryptography mailing list