Richard P. Stanley Seminar in Combinatorics: Mitali Bafna (MIT)

Friday, February 16, 2024 at 3:00pm to 4:00pm

Building 2, 139
182 MEMORIAL DR, Cambridge, MA 02139

Speaker:  Mitali Bafna (MIT)

Title:         Direct Product Testing on High Dimensional Expanders

Abstract:

The problem of testing direct product functions lies at the intersection of many areas within theoretical computer science, such as error correcting codes, probabilistically checkable proofs (PCPs), hardness amplification and property testing. We want to efficiently encode a function from [n] to {0,1} using local views in a way that admits local testability and the direct product encoding gives us the restriction of f on various subsets of [n]. A set system is said to support a direct product test when the following property holds: whenever a natural 2-query test passes with noticeable probability, the encoding is correlated to a direct-product encoding. We study the question of what hypergraph expansion properties are required of the set systems that support a direct product test in the list-decoding regime. In contrast to the unique-decoding regime, we show that spectral expansion is insufficient and the set-system must additionally possess a form of topological expansion called coboundary expansion. This also turns out to be sufficient, thus giving us a characterization of such set systems. In a recent work we build sparse set systems with coboundary expansion, using the simplicial complexes constructed by Chapman and Lubotzky, thus showing the existence of constant degree direct product testers in the list-decoding regime.

Based on joint works with Noam Lifshitz and Dor Minzer.

 

Event Type

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

Public, Students, Faculty, MIT Community, Alumni

Events By School

School of Science

Tags

stanley, Seminar, mathematics, combinatorics, MITMath, mitmathematics, stanleyseminar

Website

https://math.mit.edu/combin/

Department
Department of Mathematics
Hashtag

#mitmath

Contact Email

plouie@mit.edu

Add to my calendar

Recent Activity