The Taub Faculty of Computer Science Events and Talks

One of the key components in PCP constructions are agreement tests. In agreement testing the tester is given access to subsets of fixed size of some set, each equipped with an assignment. The tester is then tasked with testing whether these local assignments agree with some global assignment over the entire set. One natural generalization of this concept is the case where, instead of a single assignment to each local view, the tester is given access to $\ell$ different assignments for every subset. The tester is then tasked with testing whether there exist $\ell$ global functions that agree with all of the assignments of all of the local views. In this talk I will present a recent result that shows that if the subsets form a (sufficiently good) high dimensional expander then they support list agreement testing under mild assumptions on the local assignments. In addition, I will also show that those mild assumptions are necessary for list agreement. I will not assume any prior knowledge of high dimensional expanders. Based on a joint work with Tali Kaufman