New Direct Sum Tests
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910605702594560 |
|---|---|
| author | Westover, Alek Yu, Edward Zheng, Kai |
| author_facet | Westover, Alek Yu, Edward Zheng, Kai |
| contents | 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 $ε$-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 \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10464 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New Direct Sum Tests Westover, Alek Yu, Edward Zheng, Kai Computational Complexity 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 $ε$-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 \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. |
| title | New Direct Sum Tests |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2409.10464 |