These lecture notes are in draft form and will be updated in the future.
Please use as you wish and be sure to email me with comments/complaints.
These are lecture notes from a graduate seminar I taught in 2016. They notes cover the basic theory of locally-decodable codes, known construction and lower bounds, with a focus on linear codes. The selection of topics is highly personal and reflects my particular interests and teaching constraints.
- Lecture 1 - Basic definitions. Structure theorem for LDCs.
- Lecture 2 - Lower bounds for two-query codes.
- Lecture 3 - LDCs from low degree polynomials over finite fields.
- Lecture 4 - Lower bounds for general LDCs (Katz-Trevisan)
- Lecture 5 - Matching Vector Codes.
- Lecture 6 - Construction of Matching Vector Families (Grolmusz)
- Lecture 7 - Private Information Retrieval (PIR)
- Lecture 8 - Locally Correctable Codes
- Lecture 9 - LDCs and LCCs over the real/complex numbers.