# List Decoding of Error-Correcting Codes: Winning Thesis of the 2002 ACM Doctoral Dissertation Competition

Springer Science & Business Media, Nov 29, 2004 - Computers - 350 pages
How can one exchange information e?ectively when the medium of com- nication introduces errors? This question has been investigated extensively starting with the seminal works of Shannon (1948) and Hamming (1950), and has led to the rich theory of “error-correcting codes”. This theory has traditionally gone hand in hand with the algorithmic theory of “decoding” that tackles the problem of recovering from the errors e?ciently. This thesis presents some spectacular new results in the area of decoding algorithms for error-correctingcodes. Speci?cally,itshowshowthenotionof“list-decoding” can be applied to recover from far more errors, for a wide variety of err- correcting codes, than achievable before. A brief bit of background: error-correcting codes are combinatorial str- tures that show how to represent (or “encode”) information so that it is - silient to a moderate number of errors. Speci?cally, an error-correcting code takes a short binary string, called the message, and shows how to transform it into a longer binary string, called the codeword, so that if a small number of bits of the codewordare ?ipped, the resulting string does not look like any other codeword. The maximum number of errorsthat the code is guaranteed to detect, denoted d, is a central parameter in its design. A basic property of such a code is that if the number of errors that occur is known to be smaller than d/2, the message is determined uniquely. This poses a computational problem,calledthedecodingproblem:computethemessagefromacorrupted codeword, when the number of errors is less than d/2.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 I 1 III 4 IV 7 V 8 VI 9 VII 10 IX 13 XI 15
 CXIV 169 CXV 171 CXVI 174 CXVII 177 CXVIII 178 CXIX 179 CXX 180 CXXI 184

 XIV 17 XVI 18 XVII 20 XX 21 XXI 22 XXIII 23 XXIV 24 XXVI 26 XXVII 28 XXVIII 29 XXX 33 XXXII 34 XXXIII 35 XXXIV 37 XXXV 39 XXXVI 41 XXXVII 43 XXXVIII 45 XXXIX 46 XL 47 XLI 48 XLII 50 XLIV 55 XLV 56 XLVI 60 XLVIII 62 L 63 LI 64 LII 67 LIII 68 LIV 71 LVI 72 LVII 76 LIX 79 LXI 80 LXII 81 LXIV 85 LXV 88 LXVI 89 LXVII 90 LXVIII 91 LXIX 95 LXXI 96 LXXII 97 LXXIII 98 LXXV 100 LXXVI 102 LXXVII 103 LXXVIII 105 LXXIX 108 LXXX 111 LXXXI 113 LXXXII 114 LXXXIII 117 LXXXIV 121 LXXXVI 122 LXXXVII 126 LXXXVIII 129 LXXXIX 132 XC 134 XCI 136 XCII 137 XCIII 138 XCIV 141 XCV 142 XCVI 146 XCVIII 148 XCIX 149 C 151 CI 152 CIII 153 CV 154 CVI 155 CVII 156 CIX 159 CX 160 CXI 161 CXII 162 CXIII 165
 CXXII 186 CXXIII 187 CXXV 188 CXXVI 192 CXXVII 195 CXXVIII 198 CXXIX 199 CXXX 202 CXXXI 205 CXXXII 206 CXXXIII 208 CXXXIV 210 CXXXV 213 CXXXVI 215 CXXXVIII 216 CXXXIX 218 CXL 221 CXLI 225 CXLII 227 CXLIII 228 CXLV 231 CXLVI 234 CXLVII 235 CXLVIII 236 CXLIX 239 CL 242 CLI 243 CLII 244 CLIII 245 CLIV 249 CLV 251 CLVII 252 CLVIII 253 CLIX 254 CLXI 256 CLXII 257 CLXIII 258 CLXIV 259 CLXV 262 CLXVI 265 CLXIX 266 CLXX 268 CLXXI 270 CLXXII 272 CLXXIV 275 CLXXV 276 CLXXVI 277 CLXXVII 279 CLXXVIII 284 CLXXIX 285 CLXXX 286 CLXXXI 288 CLXXXII 289 CLXXXIV 291 CLXXXV 294 CLXXXVI 297 CLXXXVII 298 CLXXXVIII 299 CLXXXIX 300 CXC 302 CXCI 304 CXCII 308 CXCIII 309 CXCIV 310 CXCV 311 CXCVI 313 CXCVII 315 CXCIX 318 CC 320 CCI 324 CCIII 325 CCV 329 CCVII 330 CCIX 331 CCX 333 CCXII 336 CCXIII 348 Copyright