ECCC-Report TR20-164https://eccc.weizmann.ac.il/report/2020/164Comments and Revisions published for TR20-164en-usSat, 08 May 2021 10:48:41 +0300
Revision 1
| Direct Sum and Partitionability Testing over General Groups |
Gautam Prakriya,
Andrej Bogdanov
https://eccc.weizmann.ac.il/report/2020/164#revision1A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. This generalizes a result of Dinur and Golubev (RANDOM 2019) which is tailored to the target group $\mathcal{G} = \mathbb{Z}_2$. As a special case, we obtain an optimal affinity test for $\mathcal{G}$-valued functions on domain $\{0, 1\}^n$ under product measure. Our analysis relies on the hypercontractivity of the binary erasure channel.
We also study the testability of function partitionability over product domains into disjoint components. A $\mathcal{G}$-valued $f(x_1, \dots, x_n)$ is $k$-direct sum partitionable if it can be written as a sum of functions over $k$ nonempty disjoint sets of inputs. A function $f(x_1, \dots, x_n)$ with unstructured product range $\mathcal{R}^k$ is direct product partitionable if its outputs depend on disjoint sets of inputs.
We show that direct sum partitionability and direct product partitionability are one-sided error testable with $O((n - k)(\log n + 1/\epsilon) + 1/\epsilon)$ adaptive queries and $O((n/\epsilon) \log^2(n/\epsilon))$ nonadaptive queries, respectively. Both bounds are tight up to the logarithmic factors for constant $\epsilon$ even with respect to adaptive, two-sided error testers. We also give a non-adaptive one-sided error tester for direct sum partitionability with query complexity $O(kn^2 (\log n)^2 / \epsilon)$. Sat, 08 May 2021 10:48:41 +0300https://eccc.weizmann.ac.il/report/2020/164#revision1
Paper TR20-164
| Direct Sum and Partitionability Testing over General Groups |
Gautam Prakriya,
Andrej Bogdanov
https://eccc.weizmann.ac.il/report/2020/164A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. This generalizes a result of Dinur and Golubev (RANDOM 2019) which is tailored to the target group $\mathcal{G} = \mathbb{Z}_2$. As a special case, we obtain an optimal affinity test for $\mathcal{G}$-valued functions on domain $\{0, 1\}^n$ under product measure. Our analysis relies on the hypercontractivity of the binary erasure channel.
We also study the testability of function partitionability over product domains into disjoint components. A $\mathcal{G}$-valued $f(x_1, \dots, x_n)$ is $k$-direct sum partitionable if it can be written as a sum of functions over $k$ nonempty disjoint sets of inputs. A function $f(x_1, \dots, x_n)$ with unstructured product range $\mathcal{R}^k$ is direct product partitionable if its outputs depend on disjoint sets of inputs.
We show that direct sum partitionability and direct product partitionability are one-sided error testable with $O((n - k)(\log n + 1/\epsilon) + 1/\epsilon)$ adaptive queries and $O((n/\epsilon) \log^2(n/\epsilon))$ nonadaptive queries, respectively. Both bounds are tight up to the logarithmic factors for constant $\epsilon$ even with respect to adaptive, two-sided error testers. We also give a non-adaptive one-sided error tester for direct sum partitionability with query complexity $O(kn^2 (\log n)^2 / \epsilon)$. Mon, 09 Nov 2020 14:43:18 +0200https://eccc.weizmann.ac.il/report/2020/164