## Algorithmic Results in List DecodingAlgorithmic Results in List Decoding introduces and motivates the problem of list decoding, and discusses the central algorithmic results of the subject, culminating with the recent results on achieving "list decoding capacity." The main technical focus is on giving a complete presentation of the recent algebraic results achieving list decoding capacity, while pointers or brief descriptions are provided for other works on list decoding. Algorithmic Results in List Decoding is intended for scholars and graduate students in the fields of theoretical computer science and information theory. The author concludes by posing some interesting open questions and suggests directions for future work. |

### What people are saying - Write a review

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

### Contents

III | 3 |

IV | 5 |

V | 8 |

VI | 9 |

VII | 10 |

VIII | 13 |

IX | 15 |

X | 16 |

XXIII | 54 |

XXIV | 56 |

XXV | 59 |

XXVI | 61 |

XXVII | 62 |

XXVIII | 63 |

XXIX | 64 |

XXX | 68 |

XI | 18 |

XII | 19 |

XIII | 23 |

XIV | 29 |

XV | 32 |

XVI | 35 |

XVII | 38 |

XVIII | 42 |

XIX | 44 |

XX | 46 |

XXI | 49 |

XXII | 51 |

XXXI | 71 |

XXXII | 74 |

XXXIII | 75 |

XXXIV | 79 |

XXXV | 81 |

XXXVI | 85 |

XXXVII | 86 |

XXXVIII | 87 |

XXXIX | 88 |

XLI | 89 |

### Common terms and phrases

achieving list decoding agreement parameter algebraic approach binary codes binary symmetric channel bipartite graph block length brute-force search channel Chapter code of block codes of rate codewords coding theory coeﬃcients combinatorial Computational concatenated code constant construct decodable codes deﬁned Deﬁnition deterministic algorithm diﬀerent encoding erasure error pattern error-correcting codes expander graphs fact factor family of codes ﬁeld F ﬁnd ﬁnite ﬁeld ﬁrst folded RS code fraction of errors function Guruswami Hamming ball Hamming distance Hq(p inner code irreducible irreducible polynomial Johnson bound Johnson radius large alphabets Lemma less than q linear code list decoding algorithm list decoding capacity list recovering mial monomials multivariate interpolation noise model outer code output list polyno polynomial f(X polynomial of degree Proof random coding rate at least received word Reed–Solomon codes relative distance satisﬁes Singleton bound speciﬁc Theorem trade-oﬀ unique decoding univariate polynomial worst-case zero of multiplicity

### Popular passages

Page 96 - In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp.