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.
Topics include:
* Low degree tests
* Relaxed locally decodable and locally correctable codes
* Abstract agreement tests and direct product testing
* PCPs and gap amplification
* High dimensional expansion