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.
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.
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.