One-Sided Error Testing of Monomials and Affine Subspaces

Webpage for a paper by Oded Goldreich amd Dana Ron


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:

The running time of the testers in the positive results is linear in their query complexity.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.