Characterizing Direct Product Testing via Coboundary Expansion

View PDF

A d-dimensional simplicial complex X is said to support a direct product tester if any locally consistent function defined on its k-faces (where k\ll d) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution \mu over pairs of k-faces (A,A'), and given query access to F\colon X(k)\to\{0,1\}^k it samples (A,A')\sim \mu and checks that F[A]|_{A\cap A'} = F[A']|_{A\cap A'}. The tester should have (1) the ``completeness property'', meaning that any assignment F which is a direct product assignment passes the test with probability 1, and (2) the ``soundness property'', meaning that if F passes the test with probability s, then F must be correlated with a direct product function.
Dinur and Kaufman showed that a sufficiently good spectral expanding complex X admits a direct product tester in the ``high soundness'' regime where s is close to 1. They asked whether there are high dimensional expanders that support direct product tests in the ``low soundness'', when s is close to 0.
We give a characterization of high-dimensional expanders that support a direct product tester in the low soundness regime. We show that spectral expansion is insufficient, and the complex must additionally satisfy a variant of coboundary expansion, which we refer to as \emph{Unique-Games coboundary expanders}. Conversely, we show that this property is also sufficient to get direct product testers. This property can be seen as a high-dimensional generalization of the standard notion of coboundary expansion over non-Abelian groups for 2-dimensional complexes. It asserts that any locally consistent Unique-Games instance obtained using the low-level faces of the complex, must admit a good global solution.