Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Bogdanov, Andrej; Prakriya, Gautam https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-141028
URL:

;

Direct Sum and Partitionability Testing over General Groups

pdf-format:


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
Seminar: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue date: 2021
Date of publication: 02.07.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI