top of page

Topics in Coding Theory:

Locality and Interaction

Winter 2019/20

Syllabus

Coding theory addresses the problem of communication over imperfect channels. This field of study was initiated by Claude Shannon in the late 1940s in one of the most influential papers in all of science. Coding theory has a huge impact on real-world problems as well as many surprising applications to theoretical computer science. Error-correcting codes are pivotal in pseudo-randomness, hardness amplification, PCPs, circuit lower bounds, and the list goes on.

​

This course is about two modern, unrelated, aspects of coding theory: locality and interaction. The study of codes with "local guarantees" such as locally decodable codes and locally testable codes, owes its origin mostly to PCP though this line of work found other applications in privacy and circuit lower bounds to name a few. Error correction in the interactive setting was initiated by Schulman in the early 90s. On both aspects, there is a great deal of surprising and interesting results. Nevertheless, many fundamental, challenging problems are still wide open.

​

The particular topics that will be covered are:

​

  • Locally decodable (and correctable) codes. We will study several constructions of such codes, starting with Reed-Muller, the method of multiplicities, and the construction of codes via lifting. We will also see the state-of-the-art construction that is based on the above combined with a method of distance amplification. If time permits, we will also present constructions based on matching vectors and see a related result on private information retrieval.

  • Locally testable codes. We will study the construction of such codes based on the tensor product of codes and show the state-of-the-art result which also uses distance amplification.

  • Interactive coding theory. We will define the notion of a tree code, show how to base an interactive coding protocol based on tree codes. Lastly, we will see one tree code construction.

​

Prerequisite 

The formal prerequisite is the introductory course to complexity theory. However, throughout the course, we will make use of algebraic structures such as finite fields and other rings, in particular, polynomial rings. A solid grasp of these basic objects from abstract algebra is essential. No knowledge in coding theory is assumed - the basics will be covered at the beginning of the course.

​

Lectures 

  1. Introduction

  2. Interactive coding schemes and tree codes

  3. Schulman's coding scheme

  4. Schulman's coding scheme (cont.) and Braverman-Rao's coding scheme using poly-size alphabet

  5. Braverman-Rao's coding scheme using binary alphabet

  6. Locally decodable codes: Reed-Muller and lifting

  7. Multiplicity codes

  8. Multiplicity codes (cont.)

  9. Distance amplification and the KMRS construction

  10. LDC from matching vectors family

  11. Grolmusz's construction of matching vectors family.

  12. Dvir-Gopi's PIR

​

Assignments

  1. Assignment 1

  2. Assignment 2

  3. Assignment 3

  4. Assignment 4

​

Grade

There will be 5 or 6 homework assignments on which we will also work during the "hands-on recitation". These will determine half of the final grade. The other half is based on a presentation that will be given by each student at the end of the semester,

​

When and where 

The lecture will take place on Tuesday 9:00-12:00. Following, at 12:00-13:00, is a "hands-on recitation". The location is to be determined.

​

Reading material

The course is not based on a book but rather on research papers and surveys, including:​

​

Suggested papers for presentation​

​

Taken

​

Looking for a speaker​​

bottom of page