Access Restriction

Author Rudra, Atri ♦ Guruswami, Venkatesan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract Ever since the birth of coding theory almost 60 years ago, researchers have been pursuing the elusive goal of constructing the "best codes," whose encoding introduces the minimum possible redundancy for the level of noise they can correct. In this article, we survey recent progress in list decoding that has led to efficient error-correction schemes with an optimal amount of redundancy, even against worst-case errors caused by a potentially malicious channel. To correct a proportion ρ(say 20%) of worst-case errors, these codes only need close to a proportion ρ of redundant symbols. The redundancy cannot possibly be any lower information theoretically. This new method holds the promise of correcting a factor of two more errors compared to the conventional algorithms currently in use in diverse everyday applications.
Description Affiliation: University of Washington, Seattle, WA (Guruswami, Venkatesan) || University at Buffalo, SUNY, Buffalo, NY (Rudra, Atri)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 52
Issue Number 3
Page Count 9
Starting Page 87
Ending Page 95

Open content in new tab

   Open content in new tab
Source: ACM Digital Library