New Direct Sum Tests

Abstract

A function $f:[n{]}^d\to {\mathbb{F}}_2$ is a \defn{direct sum} if there are functions $L_i:[n]\to {\mathbb{F}}_2$ such that $f(x)={\sum }_i{L}_i(x_i)$. In this work we give multiple results related to the property testing of direct sums. Our first result concerns a test proposed by Dinur and Golubev in 2019. We call their test the Diamond test and show that it is indeed a direct sum tester. More specifically, we show that if a function $f$ is $\hat{I}\mu$-far from being a direct sum function, then the Diamond test rejects $f$ with probability at least $\hat{I}{\text{c◯}}_{n,\hat{I}\mu }(1)$. Even in the case of $n=2$, the Diamond test is, to the best of our knowledge, novel and yields a new tester for the classic property of affinity. Apart from the Diamond test, we also analyze a broad family of direct sum tests, which at a high level, run an arbitrary affinity test on the restriction of $f$ to a random hypercube inside of $[n{]}^d$. This family of tests includes the direct sum test analyzed in \cite{di19}, but does not include the Diamond test. As an application of our result, we obtain a direct sum test which works in the online adversary model of \cite{KRV}. Finally, we also discuss a Fourier analytic interpretation of the diamond tester in the $n=2$ case, as well as prove local correction results for direct sum as conjectured by Dinur and Golubev.

21 pages