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.