License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.33
URN: urn:nbn:de:0030-drops-141028
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14102/
Bogdanov, Andrej ;
Prakriya, Gautam
Direct Sum and Partitionability Testing over General Groups
Abstract
A function f(x₁, … , x_n) from a product domain ?₁ × ⋯ × ?_n to an abelian group ? is a direct sum if it is of the form f₁(x₁) + ⋯ + 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 ? = ℤ₂. As a special case, we obtain an optimal affinity test for ?-valued functions on domain {0, 1}ⁿ 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 ?-valued f(x₁, … , 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₁, … , x_n) with unstructured product range ℛ^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/ε) + 1/ε) adaptive queries and O((n/ε) log²(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(kn² (log n)² / ε).
BibTeX - Entry
@InProceedings{bogdanov_et_al:LIPIcs.ICALP.2021.33,
author = {Bogdanov, Andrej and Prakriya, Gautam},
title = {{Direct Sum and Partitionability Testing over General Groups}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {33:1--33:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14102},
URN = {urn:nbn:de:0030-drops-141028},
doi = {10.4230/LIPIcs.ICALP.2021.33},
annote = {Keywords: Direct Sum Test, Function Partitionability, Hypercontractive Inequality, Property Testing}
}
|
Keywords: |
|
Direct Sum Test, Function Partitionability, Hypercontractive Inequality, Property Testing |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
