Revision #2 Authors: Oded Goldreich, Dana Ron

Accepted on: 28th February 2022 14:41

Downloads: 177

Keywords:

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.

The current version eliminates some inaccuracies and provides a more detailed and clear exposition.

In particular, Section 5 was revised most extensively.

Revision #1 Authors: Oded Goldreich, Dana Ron

Accepted on: 9th May 2020 00:05

Downloads: 395

Keywords:

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.

Reporting of an improved lower bound by Nader Bshouty.

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.