Richard P. Stanley Seminar in Combinatorics: Direct Product Testing on High Dimensional Expanders

SEMINARS, HARVARD-MIT COMBINATORICS

Speaker:

Mitali Bafna - MIT

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. Building set systems with these expansion properties would thus lead to the ultimate form of efficient direct product testers and perhaps also allow for efficient hardness amplification.

Based on joint work with Dor Minzer (https://eccc.weizmann.ac.il/report/2023/120/)

===============================

For more info, see https://math.mit.edu/combin/