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 4query 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 kdirect 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 onesided 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, twosided error testers. We also give a nonadaptive onesided 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:133:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14102},
URN = {urn:nbn:de:0030drops141028},
doi = {10.4230/LIPIcs.ICALP.2021.33},
annote = {Keywords: Direct Sum Test, Function Partitionability, Hypercontractive Inequality, Property Testing}
}
02.07.2021
Keywords: 

Direct Sum Test, Function Partitionability, Hypercontractive Inequality, Property Testing 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 