ECCC-Report TR13-067https://eccc.weizmann.ac.il/report/2013/067Comments and Revisions published for TR13-067en-usThu, 20 Jun 2013 14:21:14 +0300
Revision 1
| On Multiple Input Problems in Property Testing |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2013/067#revision1We 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$.Thu, 20 Jun 2013 14:21:14 +0300https://eccc.weizmann.ac.il/report/2013/067#revision1
Paper TR13-067
| On Multiple Input Problems in Property Testing |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2013/067We 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$.Thu, 02 May 2013 10:43:27 +0300https://eccc.weizmann.ac.il/report/2013/067