On Multiple Input Problems in Property Testing
Webpage for a paper by Oded Goldreich
Abstract
We consider three types of multiple input problems
in the context of property testing.
Specifically, for a property $\Pi\subseteq\bitset^n$,
a proximity parameter $\epsilon$, and an integer $m$,
we consider the following problems:
- 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^\xth$ bit satisfies the requirements from
an $\epsilon$-tester for $\Pi$ regarding the $i^\xth$ input;
that is, for each $i$, the $i^\xth$ output bit should be 1
(w.p. $\geq2/3$) if the $i^\xth$ input is in $\Pi$,
and should be 0 (w.p. $\geq2/3$)
if the $i^\xth$ input is $\epsilon$-far from $\Pi$.
- Direct $m$-Product Problem for $\Pi$ and $\epsilon$:
Given a sequence of $m$ inputs, output 1 (w.p. $\geq2/3$)
if all inputs are in $\Pi$, and output 0 (w.p. $\geq2/3$)
if at least one of the inputs is $\epsilon$-far from $\Pi$.
- The $m$-Concatenation Problem for $\Pi$ and $\epsilon$:
Here one is required to $\epsilon$-test the $m$-product of $\Pi$; that is,
the property $\Pi^{m}=\{(x_1,...,x_m):\forall i\in[m]\;x_i\in\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$.
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.