Agreement Testing and Small Set Mixing in High Dimensional Expanders

Start Date: December 13, 2023
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Yotam Dikstein - Institute for Advanced Study
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
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).

Events