Monthly Archives: August 2024

News for July 2024

This month we have only one paper. I imagine the community will be on fire when we come back with our news for August.

Constant Degree Direct Product Testers with Small Soundness by Mitali Bafna, Noam Lifshitz, and Dor Minzer (arXiv) (Please excuse my lack of technical comfort with the contents of this paper. Corrections Welcome) As the title indicates, and the authors also emphasize, the primary goal of the featured paper is to construct direct product testers with constant degree. Let us try to unpack this a little by first understanding what does a direct product test mean. So I have this function \(f \colon [n] \to \{0,1\}\). I give you access to this function in an indirect way via a table \(F\) to which you have query access. The central task in direct product testing is to check whether \(F\) is a valid encoding of \(f\) by querying \(F\) on a small number of locations. This paper focuses on those properties which you can test with two queries. Dinur and Kaufman noted that high dimensional expanders can be leveraged towards obtaining \(2\)-query direct product testers. The main result of this paper shows that there are high dimensional expanders for which the Dinur-Kaufman direct product test has small soundness.