A Boolean function f : t0, 1u n ? t0, 1u is k-linear if it returns the sum (over the binary field F2) of k coordinates of the input. In this paper, we study property testing of the classes k-Linear, the class of all k-linear functions, and k-Linear?, the class Yk j“0 j-Linear. We give a non-adaptive distribution-free two-sided -tester for k-Linear that makes O ? k log k ` 1 ˙ queries. This matches the lower bound known from the literature. We then give a non-adaptive distribution-free one-sided -tester for k-Linear? that makes the same number of queries and show that any non-adaptive uniform-distribution one-sided -tester for k-Linear must make at least ??pkqlog n ` ?p1{ q queries. The latter bound, almost matches the upper bound Opk log n ` 1{ q known from the literature. We then show that any adaptive uniform-distribution one-sided -tester for k-Linear must make at least ??p ? kqlog n ` ?p1{ q queries.
展开▼
