About the Courses

Advances in Error-correction: List Decoding and Polar Coding
(Venkatesan Guruswami)

Error-correcting codes provide a judicious way to add redundancy to data in order to enable its recovery even when corrupted by various forms of noise. The basic challenge in coding theory is to construct codes with minimum possible redundancy for various noise models and requirements on the decoder, along with efficient algorithms for error correction using those codes. Over the decades, this subject has witnessed a rich body of work, drawing upon diverse techniques from combinatorics, linear algebra, graph theory, probability, information theory, and algebraic geometry to construct good codes. In addition to their crucial role in safeguarding data against the adverse effects of noise during communication and storage, error-correcting codes have emerged as an important tool underlying many advances in theoretical computer science.

After a brisk introduction to the basic motivations and concepts of coding theory and some of the classical code constructions (some of this might be assigned as reading material before the course), the course will give a glimpse into some recent advances in coding theory such as list decodable codes that can correct an error fraction as large as the redundancy of the code, and polar codes for achieving Shannon capacity in probabilistic channel models. The course may also briefly touch upon some of the rich connections between coding theory and pseudorandomness.

Beyond any pre-assigned reading on coding and information theory basics, no explicit background should be required other than familiarity with basics of linear algebra, probability, and finite fields.

Codes with Local Decoding Procedures
(Sergey Yekhanin)

Error correcting codes allow senders to add redundancy to messages, encoding bit strings representing messages into longer bit strings called codewords, in a way that the message can still be recovered even if a fraction of the codeword bits are corrupted. In certain settings however the receiver might not be interested in recovering all the message, but rather seek to quickly recover just a few coordinates of it. Codes that allow one to recover individual message coordinates extremely fast (locally), from accessing just a small number of carefully chosen coordinates of a corrupted codeword are said to admit a local decoding procedure. Such codes have recently played an important role in several areas of theoretical computer science and have also been used in practice to provide reliability in large distributed storage systems.

In this course we will survey existing constructions of codes with local decoding procedures as well as their main applications. The course assumes basic familiarity with the properties of finite fields and is otherwise self-contained.