Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

One-Sided Error Testing of Monomials and Affine Subspaces

RSS-Feed




Revision #1
Authors: Oded Goldreich, Dana Ron
Accepted on: 9th May 2020 00:05
Downloads: 58
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
Downloads: 113
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