Topics in Coding Theory

Wednesdays at 14:30-16:30, Room 208 (Math 2)

Irit Dinur

We will cover advanced topics in coding theory focusing on properties and constructions beyond the basics of rate/distance/decoding-algorithms. We will see several notions of locality in codes that guarantee both resilience and usability. We will explore a variety of techniques and constructions of codes ranging from algebraic to combinatorial. Finally, we will see some applications of error-correcting codes both within TCS, and beyond.

Administrative stuff: Please sign up here for a lecture. Also, please sign up here to join the seminar's mailing list.


A basic course in coding theory, see here, or for example several chapters in this book.

Part I: Locally Decodable Codes (LDCs)

Locally decodable codes "LDCs" are codes that allow very quick random-access retrieval of information. Unlike classical codes, to retrieve a piece of information you do not need to read the entire codeword. We will use Yekhanin's survey paper as the main text.

  1. Definitions, Reed-Muller, local decoding & params.

  2. Multiplicity Codes

  3. Matching Vectors codes

  4. Lower bounds

  5. * PIR - Private Information Retrieval (Dvir-Gopi) 

  6. * Efremenko: from irreducible representations to LDCs

Part II: Constructions with expanders

Expander graphs are pseudorandom graphs that are sparse but behave as if they were dense. There are many ways in which expanders are applied towards constructing error-correcting codes. These have various desirable properties akin to LDCs: local correctability, local testability, symmetry, good rate/distance tradeoffs, and more.

  1. LCCs with n^\epsilon queries [HOW]
  2. LCC, LTC via expanders [KORS, GKORS]

  3. Ta-Shma’s Zigzag code [paper]

  4. Spielman’s linear-time decoding of a code [paper]

  5. Highly symmetric expander codes [paper]

Part III: Various topics

In the last part of the seminar we will explore various directions including applications of error-correcting codes in complexity, and in real-life applications (LRCs). We will take a look at quantum codes

  1. Applications of coding theory:

  1. Quantum Codes

  2. Locally Repairable Codes (LRCs) - (lecture)