Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-164 | 9th November 2020 08:33

Direct Sum and Partitionability Testing over General Groups


Authors: Andrej Bogdanov, Gautam Prakriya
Publication: 9th November 2020 14:43
Downloads: 162


A 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)$.

ISSN 1433-8092 | Imprint