On Multiple Input Problems in Property Testing

Webpage for a paper by Oded Goldreich


Abstract

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

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

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.