2019 - 2020

0368-4194   Topics in Coding Theory: Locality and Interaction  
View groups
Course description

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.

Please see the course website for more details.

accessibility declaration

tel aviv university