Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Summer 2007 

Graduate seminar "Fuzzy Coding"


Michael Nüsken, Prof. Dr. Joachim von zur Gathen

Time & Place

Wednesday, 15:00 - 17:00, b-it 1.25.
Organizational meeting: Tuesday, 3 April 2007,
16:00, b-it 1.25 (cosec meeting room).
First session: Wednesday, 2 May 2007, 15:00.


Ok, we changed the topic. We will deal with list decoding this semester. Coding theory is a rather old topic. It started evolving when electro-magnetic transmissions were coming up. The need to tolerate errors during the transmission made it necessary to find better ways than just repeating bits. Actually, you need to repeat each bit three times to get something better than just sending any bit once. The classical task is to encode short words to slightly longer words, and to decode the possibly distorted long words back to the short words. One single bit flip inside the long word should still lead to the original word. Or maybe two bit flips... Essentially, we introduce redundancy. Only we want to do that cleverly, as the increase in length decreases our transmission rate. Classically, the research focused on finding sets of code words that have large distance to each other, so that when only half that many bits are wrong the code word can still be found. Encoding and decoding were not important in this context. List decoding actually is "fuzzy decoding". A cleartext is encoded by a codeword. The possibly distorted codeword is decoded and some possibilities, ie. a list, for the original codeword are given. Formally, the decoding problem is given any word to find all codewords that differ in at most e places from the given word. Clearly, if that shall be efficient the output list must be short. If we limit the list length to 1 we have the classical problem. Further the obvious question is what the use of such a "fuzzy" code might be, if we are not able to decode uniquely. Actually, we will shed light on this. We will follow the book Guruswami (2004).


Note that this is a working seminar. Its sessions might be less structured, talks more ad-hoc and with more discussion than usual. A session might thus expand and use another week or shrink.

Wednesday 02.05.2007 / 09.05.2007 :
Michael Nüsken, Introduction & Preliminaries
Wednesday 09.05.2007 /Tuesday 15.05.2007 1300:
Michael Nüsken, Johnson-Type Bounds and Applications to List Decoding
Wednesday 06.06.2007 1400 - 1715:
Daniel Loebenberger, Limits to List Decodability
Wednesday 13.06.2007 /Wednesday 20.06.2007 :
Damien Vergnaud, List Decodability vs. Rate
Wednesday 27.06.2007 :
NN, Reed-Solomon and Algebraic-Geometric Codes
Wednesday 04.07.2007 :
NN, A Unified Framework for List Decoding of Algebraic Codes
Wednesday 11.07.2007 :
NN, List Decoding of Concatenated Codes
NN, New, Expander-Based List Decodable Codes
NN, List Decoding from Erasures
NN, Linear-Time Codes for Unique Decoding
NN, Sample Applications Outside Coding Theory


Contact Michael Nüsken.



Media Informatics, Communication Skills.
University of Bonn - Computer Science, A or A1.
University of Bonn - Mathematics, ??.

Imprint, webmaster & more