Goldreich, Oded
On Multiple Input Problems in Property Testing
Abstract
We consider three types of multiple input problems in the context of property testing. Specifically, for a property Pi (of nbit long strings), a proximity parameter epsilon, and an integer m, we consider the following problems:
(1) Direct mSum 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 ith bit satisfies the requirements from an epsilontester for Pi regarding the ith input; that is, for each i, the ith output bit should be 1 (w.p. at least 2/3) if the ith input is in Pi, and should be 0 (w.p. at least 2/3) if the ith input is epsilonfar from Pi.
(2) Direct mProduct 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 epsilonfar from Pi.
(3) The mConcatenation Problem for Pi and epsilon: Here one is required to epsilontest the mproduct of Pi; that is, the property that consists of the mwise Cartesian product of Pi.
We show that the query complexity of the first two problems
is Theta(m) times the query complexity of epsilontesting 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 epsilontesting Pi.
All upper bounds are shown via efficient reductions.
We also consider the nonadaptive and onesided error versions of these problems. The only significant deviation from the picture in the general (adaptive and twosided error) model is that the onesided error query complexity of the Direct Product Problem equals Theta(m) times the (twosided error) query complexity of epsilontesting Pi plus Theta(1) times the onesided error query complexity of epsilontesting Pi.
BibTeX  Entry
@InProceedings{goldreich:LIPIcs:2014:4733,
author = {Oded Goldreich},
title = {{On Multiple Input Problems in Property Testing}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {704720},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4733},
URN = {urn:nbn:de:0030drops47336},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.704},
annote = {Keywords: Property Testing, Direct Sum Theorems, Direct Product Theorems, Adaptive vs Nonadaptive queries, OneSided Error vs TwoSided Error}
}
04.09.2014
Keywords: 

Property Testing, Direct Sum Theorems, Direct Product Theorems, Adaptive vs Nonadaptive queries, OneSided Error vs TwoSided Error 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Issue date: 

2014 
Date of publication: 

04.09.2014 