List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
type: Item
instance of: scholarly article
title: List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
zbMATH Open document ID: 1075.94001
author: Venkatesan Guruswami
published in: Lecture Notes in Computer Science
publication date: 2005-06-13T00:00:00Z
review text: This thesis (or LN in CS) presents some spectacular new results in the area of decoding algorithms for error correcting codes. Specifically, it shows the notion of ``list decoding'' can be applied to recover from far more errors, for a wide variety of error correcting codes, than those achievable before. Then this book presents a detailed investigation of list decoding and proved its potential, feasibility, and importance as a combinational and algorithmic concept. List decoding permits recovery from errors well beyond the \(d/2\) barrier, and opens up the possibility of meaningful error from large amounts of noise. So in: Ch.1: Introduction. The key technical notion underlying the ``list decoding''. This is defined and the contributions are explained in details. Ch.2: Preliminaries and Monograph Structure. Presents a comprehensive investigation of the notion of list decoding. The book consists three parts. Specifically: Part I: Combinatorics. The minimum distance is not the only approach to get good list decodable codes, as directly optimizing the list decoding radius can lead to better trade - offs of the rate of the code. Ch.3: Johnson-Type Bounds and Applications to List Decoding. This chapter and the next explore the relation and minimum distance of a code. Ch.4: Limits to list decodability. As the previous chapter, this concerns in extent about the distance vs List Decodability relation and are not directly concerned about the rate. Ch.5: List Decodability vs Rate. The chapter studies the trade - offs between list decoding radius and the rate of code families. Part II: Algorithms. The algorithmic results enable us to get new constructions of binary codes of good rate and excellent algorithmic decodability. Ch.6: Reed- Solomon and Algebraic Codes. The presentation polynomial time list decoding algorithms for two important classes of algebraic codes, mainly Reed-Solomon and algebraic geometric codes are represented in this chapter. Ch.7: A Unified Framework for …
Mathematics Subject Classification ID: 94-02
Mathematics Subject Classification ID: 94B35
zbMATH DE Number: 2175706
zbMATH Keywords: Johnson-Type Bounds
zbMATH Keywords: minimum distance
zbMATH Keywords: list decoding radius
zbMATH Keywords: binary codes
zbMATH Keywords: Reed- Solomon and Algebraic codes
zbMATH Keywords: pseudolinear codes
zbMATH Keywords: multi-concatenated codes
zbMATH Keywords: noise model of erasures
reviewed by: Dimitris Voukalis
MaRDI profile type: Publication
full work available at URL: b104335
OpenAlex ID: W1580365030
DOI: 10.1007/B104335
description: scientific article; zbMATH DE number 2175706