2026-07-25T06:36:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4733 2024-03-06T10:35:20Z ddc:004 open_access

On Multiple Input Problems in Property Testing Goldreich, Oded Property Testing Direct Sum Theorems Direct Product Theorems Adaptive vs Nonadaptive queries One-Sided Error vs Two-Sided Error We consider three types of multiple input problems in the context of property testing. Specifically, for a property Pi (of n-bit long strings), a proximity parameter epsilon, and an integer m, we consider the following problems: (1) Direct m-Sum Problem for Pi and epsilon: Given a sequence of m inputs, output a sequence of m bits such that for each i in [m] the i-th bit satisfies the requirements from an epsilon-tester for Pi regarding the i-th input; that is, for each i, the i-th output bit should be 1 (w.p. at least 2/3) if the i-th input is in Pi, and should be 0 (w.p. at least 2/3) if the i-th input is epsilon-far from Pi. (2) Direct m-Product Problem for Pi and epsilon: Given a sequence of m inputs, output 1 (w.p. at least 2/3) if all inputs are in Pi, and output 0 (w.p. at least 2/3) if at least one of the inputs is epsilon-far from Pi. (3) The m-Concatenation Problem for Pi and epsilon: Here one is required to epsilon-test the m-product of Pi; that is, the property that consists of the m-wise Cartesian product of Pi. We show that the query complexity of the first two problems is Theta(m) times the query complexity of epsilon-testing Pi, whereas (except in pathological cases) the query complexity of the third problem is almost of the same order of magnitude as the query complexity of the problem of epsilon-testing Pi. All upper bounds are shown via efficient reductions. We also consider the nonadaptive and one-sided error versions of these problems. The only significant deviation from the picture in the general (adaptive and two-sided error) model is that the one-sided error query complexity of the Direct Product Problem equals Theta(m) times the (two-sided error) query complexity of epsilon-testing Pi plus Theta(1) times the one-sided error query complexity of epsilon-testing Pi. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oded Goldreich 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.704 urn:nbn:de:0030-drops-47336 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.704 eng https://creativecommons.org/licenses/by/3.0/legalcode