Teacher: Irit
Dinur
Location: Ziskind 155
Time: Wednesdays 14:15 - 16:30 (first meeting 20 July, 2025)
[zoom link]
Please fill this form to get announcements about the course, including the zoom link.
When studying large complex objects (a large set of data or a large computation) we often look at small pieces of it that are easy to understand, and then study how these relate to the global object. This question occurs in many scenarios in computer science: in error correcting codes, in probabilistically checkable PCPs, in hardness of approximation of constraint satisfaction problems (CSPs), and more.
We will look into some nice local to global techniques and theorems, and show how they apply in a variety of settings. We will start with low degree tests which are a cornerstone of probabilistically checkable proofs (PCPs); move to more abstract notions of agreement tests, and continue with high dimensional expanders (HDX) and how they fit into this picture.
Lecture notes: [Lecture 1]
Here is a tentative list of topics we might cover in the class: