UC San Diego

With ever increasing amount of digital data being generated everyday on various platforms the need for data storage techniques has increased tremendously. A central component of all data storage techniques are error correction codes. An ideal error correcting code is tolerant to noise, minimally redundant and computationally inexpensive. Figuring out the optimal trade offs between these properties forms the central theme of coding theory. In this thesis we will formulate a central question that underlies the computational performance of all error correction codes and answer this question in various contexts.