Search Results

A function f:[n]^{d} → 𝔽₂ is a direct sum if there are functions L_i:[n] → 𝔽₂ such that f(x) = ∑_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 [Dinur and Golubev, 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 ε-far from being a direct sum function, then the Diamond test rejects f with probability at least Ω_{n,ε}(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 [Dinur and Golubev, 2019], 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 [Iden Kalemaj et al., 2022]. 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, 2019].