ECCC-Report TR20-068https://eccc.weizmann.ac.il/report/2020/068Comments and Revisions published for TR20-068en-usSat, 09 May 2020 00:05:52 +0300
Revision 1
| One-Sided Error Testing of Monomials and Affine Subspaces |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2020/068#revision1We 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.
Sat, 09 May 2020 00:05:52 +0300https://eccc.weizmann.ac.il/report/2020/068#revision1
Paper TR20-068
| One-Sided Error Testing of Monomials and Affine Subspaces |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2020/068
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.
Sun, 03 May 2020 23:04:44 +0300https://eccc.weizmann.ac.il/report/2020/068