2026-07-21T03:18:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22722 2026-04-17T05:32:47Z ddc:004 open_access

New Direct Sum Tests Westover, Alek Yu, Edward Zheng, Kai Zhe Linearity testing Direct sum Grids 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alek Westover and Edward Yu and Kai Zhe Zheng 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.94 urn:nbn:de:0030-drops-227229 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.94 eng https://creativecommons.org/licenses/by/4.0/legalcode