Oded Goldreich

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

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu

We give a strong direct sum theorem for computing $XOR \circ g$. Specifically, we show that the randomized query complexity of computing the XOR of $k$ instances of $g$ satisfies $\bar{R}_\varepsilon(XOR \circ g)=\Theta(\bar{R}_{\varepsilon/k}(g))$. This matches the naive success amplification bound and answers a question of Blais and Brody.

As a ... more >>>