Yotam Dikstein, Institute for Advanced Study

Abstract

Agreement testing (aka direct product testing) is a main component in most PCP constructions and in many locally testable codes. We will introduce these tests and see how they can be viewed as an interactive protocol that tests consistency among provers.

After this we will introduce high dimensional expanders (HDXs). These are sparse approximations of the complete hypergraph that have found quite a few applications in TCS. We will see a how a simple ``small set mixing'' property of HDXs translates to sound agreement tests, and time permitting, discuss the connections of this property to sparse samplers/extractors.

This is a joint work with Max Hopkins (UCSD).

See: https://theory.cs.rutgers.edu/theory_seminar