Coding Theory and Applications

Fall **2020**

**Instructor :** Alexander Barg

^{(*)}Department of ECE, ^{(*)}Inst. for Systems Research, ^{(*)}Department of CS, ^{(*)}Department of Mathematics

Office: 2361 A.V. Williams Building. E-mail: abarg at umd dot edu

**Class times:**

__Lectures:__ Streaming online TuTh 2:00 - 3:15

**Instructor availability outside class hours:** Please send me an email, including an online meeting request

**Course Homepage:** http://www.ece.umd.edu/~abarg/ECC

**Course description:** This is a graduate-level introduction to Coding Theory with an emphasis on essential constructions and algorithms. We will cover several foundational methods that are widely used in modern research in coding theory and adjacent areas of CS and discrete mathematics. The first part covers basic concepts of coding theory including linear codes and bounds on codes. We continue with algebraic constructions such as Reed-Solomon codes and their extensions, and their list decoding algorithms. The second part is devoted to topics being developed in current research, including polar codes (as an explicit way to achieve the Shannon capacity), codes on graphs, codes for the cloud (locally recoverable codes, regenerating codes), codes for storage and index coding, other applications (inference and security). The course will take students to the forefront of research in some of the mentioned topics, enabling them to follow current research literature in coding theory and applications.

** Prerequisites** The course focuses on mathematical reasoning, so general mathematical maturity and previous experience of similar kind is essential. Most of the results are established from the first principles, so no specific background is required (except for good knowledge of basic linear algebra).

**Textbook:** No required textbook. The lectures draw on multiple sources, some of which are listed below.

**Grading:** Homeworks (1/3), Course project/End of course presentation (1/3), Take home final exam (1/3)

Project topics and materials will be distributed halfway into the course (please wait for the announcement). Please take a look at the 2019 class (on a different subject) to get an idea of the project style.

**Course contents:** We plan to cover the following topics:

- Basic notions of linear codes, bounds on codes
- Algebraic codes, list decoding and its limits
- Asymptotically good codes: Random and efficiently constructible
- Codes on graphs and their decoding (expander and LDPC codes)
- Threshold phenomenon: Channel capacity, Polar codes, Reed-Muller codes
- Applications: Coding for storage (coding for the cloud), Index coding.

**Home assignments:** | HW1 Solutions | HW2 Solutions | HW3 Solutions |
**Final exam:** Problems Solutions

Here is a List of Papers for the course project (the linked version is the most recent one).

[GRS], Sec. 4.1-4.4; [MS], Sec. 5.1; [R], Sec.4.4.

The 1963 paper by J. MacWilliams; Delsarte, Goethals and Seidel's 1977 paper

Recent applications to spherical codes and lattices.

[GRS], Sec.4.4, Sec. 4.2, and Ch.2. my paper with G.D. Forney;

Madhu Sudan's Lectures 2,3; [GRS] Ch.6; my paper with G.D. Forney; UMass Lect.7 by Arya Mazumdar.

[R], Ch.3; [MS], Sec.4.1-4.3; Old class notes (Lec.11,12,17)

[GRS], Ch.10, Sec.5.2-5.3; [MS], Sec.10.11; [R] Ch.12

[GRS], Ch.15; Sudan's materials for Lec.9 (Harvard); my notes Pt.II, pp.34-35

[GRS], Ch.15; [R] Sec.9.3-9.5; [JH] Ch. 12

[GRS], Ch.15; Ch.7

Reading for (2): [B] Ch.9 (first 4 sections); Sec. 10.3, 10.4

(not in textbooks); Tanner's paper

Sudan's lectures 13,14; Zemor's algorithm: wikipedia and paper

Reading for (1) [GRS] Ch.12; my 2003 notes

Eren Sasoglu's thesis here or here

Arikan's 2009 paper

Youtube lectures of Telatar and Urbanke

My notes

[GRS] Ch.11 (more detailed than we did in class)

consult references for Lec.18

Threshold probability paper

RM codes: [MS] Ch.13, [GRS] Ch.9,14

Recent survey of RM codes (Abbe-Shpilka-Ye)

Links between polar codes and RM codes

For (2) I will follow Abbe-Shpilka-Ye; here's the original paper by Kudekar e.a.

For (2) see Yekhanin's survey below.

For (2) see: McEliece-Sarwate | Massey | Ashikhmin-Barg | Ding-Yuan |

Ozarov-Weiner The wiretap channel | Wei's paper on GHWs | Tsfasman-Vladuts: Geometric view of higher weights

Part II 4:00 - 5:30pm You are invited to attend the talk by Mary Wootters (Stanford U.)

References for IPP codes: Hollmann e.a. IPP codes for 2 parents | paper on the case of many parents

12/8, 12/10 End of course presentations