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.

Prerequisites

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:

• - Hardness amplification and local list decoding

• - PCPs, LTCs, and relaxed LDCs

2. Quantum Codes

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

References

• Yekhanin's survey paper

• Venkat Guruswami's course notes.

• Zeev Dvir's lecture notes 

• Anup Rao's course notes

• Ta-Shma's course on P vs. BPP.