Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-067 | 20th June 2013 14:21

On Multiple Input Problems in Property Testing

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 20th June 2013 14:21
Downloads: 650
Keywords: 


Abstract:

We consider three types of multiple input problems in the context of property testing.
Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}
\item 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^{th}$ input;
that is, for each $i$, the $i^{th}$ output bit should be 1
(w.p. $\geq2/3$) if the $i^{th}$ input is in $\Pi$,
and should be 0 (w.p. $\geq2/3$)
if the $i^{th}$ input is $\epsilon$-far from $\Pi$.
\item 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$.
\item 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\}$.
\end{enumerate}
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$.



Changes to previous version:

Ilan Newman called our attention to the fact that Lemma 1.1
is implicit in the work of Feige, Raghavan, Peleg, and Upfal
("Computing with Noisy Information", SIAM Journal on Computing},
Vol. 23 (5), pages 1001--1018, 1994).
We augmented the current version accordingly.


Paper:

TR13-067 | 2nd May 2013 10:42

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\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}
\item 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^{th}$ input;
that is, for each $i$, the $i^{th}$ output bit should be 1
(w.p. $\geq2/3$) if the $i^{th}$ input is in $\Pi$,
and should be 0 (w.p. $\geq2/3$)
if the $i^{th}$ input is $\epsilon$-far from $\Pi$.
\item 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$.
\item 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\}$.
\end{enumerate}
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$.



ISSN 1433-8092 | Imprint