Loading jsMath...
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: 2675
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