__
Revision #1 to TR20-068 | 9th May 2020 00:05
__
#### One-Sided Error Testing of Monomials and Affine Subspaces

**Abstract:**
We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:

\begin{itemize}

\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has query complexity ${\widetilde{O}}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.

\item The bounded problem, in which the arity of the monomial (resp., co-dimension of the subspace) is upper bounded by a fixed parameter, has query complexity ${\widetilde{O}}(1/\epsilon)$.

\item The exact problem, in which the arity of the monomial (resp., co-dimension of the subspace) is required to equal a fixed parameter (e.g., equals~2), has query complexity ${\widetilde{\Omega}}(\log n)$, where $n$ denotes the length of the argument for the tested function.

\end{itemize}

The running time of the testers in the positive results is linear in their query complexity.

**Changes to previous version:**
Reporting of an improved lower bound by Nader Bshouty.

__
TR20-068 | 3rd May 2020 23:01
__

#### One-Sided Error Testing of Monomials and Affine Subspaces

**Abstract:**

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:

\begin{itemize}

\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has query complexity ${\widetilde{O}}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.

\item The bounded problem, in which the arity of the monomial (resp., co-dimension of the subspace) is upper bounded by a fixed parameter, has query complexity ${\widetilde{O}}(1/\epsilon)$.

\item The exact problem, in which the arity of the monomial (resp., co-dimension of the subspace) is required to equal a fixed parameter (e.g., equals~2), has query complexity ${\widetilde{\Omega}}(\log n)$, where $n$ denotes the length of the argument for the tested function.

\end{itemize}

The running time of the testers in the positive results is linear in their query complexity.