We learn from our alumni in this interaction series, often technically, sometimes semi-technically.

Mitali Bafna MIT

Mitali is a postdoc at MIT Math. Before this she did a one-year postdoc at CMU hosted by Prof. Aayush Jain and Prof. Pravesh Kothari. She graduated from Harvard in 2022 advised by Prof. Madhu Sudan and was an undergrad at IIT Madras. Her research is focussed on complexity theory and algorithms, specifically the complexity of combinatorial optimization problems, sum of squares algorithms and high dimensional expanders.

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 that constant degree direct product testers in the list-decoding regime exist.

Based on joint works with Noam Lifshitz and Dor Minzer.

Organizers