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
by
Prof. Madhu Sudan
Massachusetts Institute of Technology
Cambridge, MA
DATE: Thursday, April 10, 2003
TIME: 4:00 PM
PLACE: Stratton Hall, WPI, Room 203
ABSTRACT
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
channel.
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.
DIRECTIONS:
This WPI Cryptoseminar is being held in the Stratton Hall building on
the WPI campus. Directions to the campus can be found at
http://www.wpi.edu/About/Visitors/directions.html
ATTENDANCE:
The seminar is open to everyone and free of charge. Simply send me a
brief email if you plan to attend.
MAILING LIST:
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
http://www.ece.wpi.edu/research/crypt/seminar/index.htm
Regards,
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://www.wpi.edu/~sunar
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