Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-104 | 18th July 2022 12:02

On One-Sided Testing Affine Subspaces

RSS-Feed




TR22-104
Authors: Nader Bshouty
Publication: 18th July 2022 15:43
Downloads: 116
Keywords: 


Abstract:

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ in~[16].

We then show that any one-sided $\epsilon$-tester with proximity parameter $\epsilon<1/|F|^d$ for the class of Boolean functions that describe $(n-d)$-dimensional affine subspaces and Boolean functions that describe axis-parallel $(n-d)$-dimensional affine subspaces must make at least
$\Omega(1/\epsilon+|F|^{d-1}\log n)$ and $\Omega(1/\epsilon+|F|^{d-1}n)$ queries, respectively.
This improves the lower bound $\Omega(\log n/\log\log n)$ that is proved in~[16] for $F=GF(2)$. We also give testers for those classes with query complexity that almost match the lower bounds.



ISSN 1433-8092 | Imprint