Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR20-068 | 9th May 2020 00:05

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

Revision #1
Authors: Oded Goldreich, Dana Ron
Accepted on: 9th May 2020 00:05
Keywords:

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.

### Paper:

TR20-068 | 3rd May 2020 23:01

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

TR20-068
Authors: Oded Goldreich, Dana Ron
Publication: 3rd May 2020 23:04
Keywords:

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.

ISSN 1433-8092 | Imprint