期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-28
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A function f(x1, . . . , xn) from a product domain D1 × · · · × Dn to an abelian group G is a direct sum if it is of the form f1(x1) · · · fn(xn). 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 G = Z2. As a special case, we obtain an optimal affinity test for 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 G-valued f(x1, . . . , xn) 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(x1, . . . , xn) with unstructured product range Rk 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/) 1/) adaptive queries and O((n/) log2 (n/)) nonadaptive queries, respectively. Both bounds are tight up to the logarithmic factors for constant 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(kn2 (log n) 2/).
