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