New Direct Sum Tests
<|reference_start|>New Direct Sum Tests: 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 $\epsilon$-far from being a direct sum function, then the Diamond test rejects $f$ with probability at least $\Omega_{n,\epsilon}(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.<|reference_end|>
@article{westover2024new,
    title={New Direct Sum Tests},
    author={Alek Westover, Edward Yu, Kai Zheng},
    journal={arXiv preprint arXiv:2409.10464},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.10464},
    primaryClass={cs.CC}
}