List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition (Q1780828)

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 List Decoding of algebraic codes. Paradigms of algorithms of several known algebraic codes are given in this chapter. Ch.8: List Decoding of Concatenated Codes. The results of the previous chapters apply to codes over large alphabets (algebraic - geometric codes exist over small alphabets, but their list decodability is limited by certain barriers based on some deep results from algebraic geometry). Ch.9: New, Expander - Based List Decodable Codes. This chapter presents novel constructions of list decodable codes that address the above shortcomings (as pseudolinear codes, multi-concatenated codes et al.). Ch.10: List Decoding from Erasures. This chapter considers the noise model of erasures. Under this model the symbols at an adversarially chosen set of positions are simply erased and the rest of the symbols are transmitted with no error. Part III.: Applications. Some important applications are listed, such as cryptographic questions, traitor training et al. Ch.11: Linear Time Codes for Unique Decoding. This chapter uses techniques similar to previous chapters to built codes of very good rate together with extremely efficient unique/ unambiguous decoding algorithms. Ch.12: Sample Applications outside Coding Theory. In this chapter some sample applications of list decoding theory is discussed outside the coding theory (such as cryptography, traitor tracing et al.) and, Ch.13: Concluding Remarks. The book gives a brief summary and discusses some open questions and possible directions for future research.