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 ...
more >>>
Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{0,1}^m \to {0, 1}.
Let D^(prod) denote the maximum distributional query ... more >>>