1 Inroduction
Property testing of Boolean function was first considered in the seminal works of Blum, Luby and Rubinfeld [9] and Rubinfeld and Sudan [38] and has recently become a very active research area. See for example, [1, 2, 3, 4, 7, 8, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 25, 27, 30, 31, 33, 32, 34, 39] and other works referenced in the surveys and books [23, 24, 35, 36].
A Boolean function is said to be linear if it returns the sum (over the binary field ) of some coordinates of the input, linear if it returns the sum of coordinates, and, linear if it returns the sum of at most coordinates. The class Linear (resp. Linear and ) is the classes of all linear functions (resp. all linear functions and ). Those classes has been of particular interest to the property testing community [7, 8, 9, 10, 11, 21, 22, 24, 28, 35, 36, 37, 39].
1.1 The Model
Let and be two Boolean functions and let be a distribution on . We say that is far from with respect to (w.r.t.) if and close to w.r.t. if .
In the uniformdistribution and distributionfree property testing model, we consider the problem of testing a class of Boolean function . In the distributionfree testing model (resp. uniformdistribution testing model), the tester is a randomized algorithm that has access to a Boolean function via a blackbox oracle that returns when a string is queried. The tester also has access to unknown distribution (resp. uniform distribution) via an oracle that returns chosen randomly according to the distribution (resp. according to the uniform distribution). A distributionfree tester, [26], (resp. uniformdistribution tester) for is an tester that, given as input a distance parameter and the above two oracles to a Boolean function ,

if is far from every w.r.t. (resp. uniform distribution) then rejects with probability at least .
We will also call an tester for the class or an algorithm for testing . We say that is onesided if it always accepts when ; otherwise, it is called twosided tester. The query complexity of is the maximum number of queries makes on any Boolean function . If the query complexity is then we call the tester a query tester or a tester with query complexity .
In the adaptive testing (uniformdistribution or distributionfree) the queries can depend on the answers of the previous queries where in the nonadaptive testing all the queries are fixed in advance by the tester.
In this paper we study testers for the classes Linear and Linear.
1.2 Prior Results
Throughout this paper we assume that . Blum et al. [9] gave an query nonadaptive uniformdistribution onesided tester (called BLR tester) for Linear. Halevy and Kushilevitz, [28], used a selfcorrector (an algorithm that computes from a black box query to that is close to ) to reduce distributionfree testability to uniformdistribution testability. This reduction gives an query nonadaptive distributionfree onesided tester for Linear. The reduction can be applied to any subclass of Linear. In particular, any query uniformdistribution tester for Linear () gives a query distributionfree tester.
It is well known that if there is a query uniformdistribution tester for Linear and a query uniformdistribution tester for the class Junta^{1}^{1}1The class of boolean functions that depends on at most coordinates then there is an query uniformdistribution tester for . Since , if there is a query uniformdistribution tester for then there is an query uniformdistribution twosided tester for . Therefore, all the results for testing Junta are also true for and Linear in the uniformdistribution model.
For lower bounds on the number queries for twosided uniformdistribution testing Linear (see the table in Figure 1): For nonadaptive testers Fisher, et al. [21] gave the lower bound . Goldreich [22], gave the lower bound . In [8], Blais and Kane gave the lower bound . Then in [7], Blais et al. gave the lower bound . For adaptive testers, Goldreich [22], gave the lower bound . Then Blais et al. [7] gave the lower bound and in [8], Blais and Kane gave the lower bound . Then in [39], Saglam gave the lower bound . This bound with the trivial lower bound gives the lower bound
(1) 
for the query complexity of any adaptive uniformdistribution (and distributionfree) twosided testers.
For upper bounds for uniformdistribution twosided testing Linear, Fisher, et al. [21] gave the first adaptive tester that makes queries. In [11], Buhrman et al. gave a nonadaptive tester that makes queries for any constant . As is mentioned above, testing Linear can be done by first testing if the function is Junta and then testing if it is Linear. Therefore, using Blais [5, 6] adaptive and nonadaptive testers for Junta we get adaptive and nonadaptive uniformdistribution testers for Linear that makes and queries, respectively.
For upper bounds for twosided distributionfree testing Linear, as is mentioned above, from Halevy et al. reduction in [28], an adaptive and nonadaptive distributionfree tester can be constructed from adaptive and nonadaptive uniformdistribution testers. This gives an adaptive and nonadaptive distributionfree twosided testers for Linear that makes and queries, respectively. See the table in Figure 1.
1.3 Our Results
In this paper we prove
Theorem 1.
For any , there is a polynomial time nonadaptive distributionfree onesided tester for Linear that makes
queries.
By the reduction from to , we get
Theorem 2.
For any , there is a polynomial time nonadaptive distributionfree twosided tester for Linear that makes
queries.
For onesided testers for Linear we prove
Theorem 3.
Any nonadaptive uniformdistribution onesided tester for Linear must make at least queries.
This almost matches the upper bound that follows from the reduction of Goldreich et. al [26] and the nonadaptive deterministic exact learning algorithm of Hofmeister [29] that learns Linear with queries.
For adaptive testers we prove
Theorem 4.
Any adaptive uniformdistribution onesided tester for Linear must make at least queries.
The table in 1 summarizes all the results in the literature and our results for the class .
Upper/  OneSided/  Adaptive/  Uniform/  
Lower  TwoSided  NonAdap.  Dist. Free  Result  Reference 
Upper  TwoSided  Adaptive  Uniform  [21]  
Upper  TwoSided  Adaptive  Uniform  [6]  
Upper  TwoSided  Adaptive  Dist. Free  [28]  
Upper  TwoSided  NonAdap.  Uniform  ( Const.)  [11] 
Upper  TwoSided  NonAdap.  Uniform  [5]  
Upper  TwoSided  NonAdap.  Dist. Free  [28]  
Upper  TwoSided  NonAdap.  Dist. Free  Ours  
Lower  TwoSided  NonAdap.  Uniform  Trivial  
Lower  TwoSided  NonAdap.  Uniform  [21]  
Lower  TwoSided  NonAdap.  Uniform  [22]  
Lower  TwoSided  NonAdap.  Uniform  [7]  
Lower  TwoSided  Adaptive  Uniform  [22]  
Lower  TwoSided  Adaptive  Uniform  [7, 8]  
Lower  TwoSided  Adaptive  Uniform  [39]  
Upper  OneSided  NonAdaptive  Dist. Free  [26]  
Lower  OneSided  NonAdaptive  Uniform  Ours  
Lower  OneSided  Adaptive  Uniform  Ours 
2 Overview of the Testers and Lower Bounds
In this section we give overview of the techniques used for proving the results in this paper.
2.1 Onesided Tester for Linear
The tester for Linear first runs the tester BLR of Blum et al. [9] to test if the function is close to Linear w.r.t. the uniform distribution, where . BLR is onesided tester and therefore, if is linear then BRG accepts with probability 1. If is far from Linear w.r.t. the uniform distribution then, with probability at least , BLR rejects. Therefore, if the tester BLR accepts, we may assume that is close to Linear w.r.t. the uniform distribution. Let Linear be the function that is close to . If is linear then . This is because and the distance (w.r.t. the uniform distribution) between every two linear functions is . BLR makes queries.
In the second stage, the tester tests if (not ) is linear. Let us assume for now that we can query in every string. Since Linear, we need to distinguish between functions in Linear and functions in LinearLinear. We do that with two tests. We first test if Linear and then test if it is in Linear assuming that it is in Linear. In the first test, the tester “throws”, uniformly at random, the variables of into bins and tests if there is more than nonempty bins. If is linear then the number of nonempty bins is always less than . If it is linear for some then with high probability (w.h.p.) the number of nonempty bins is greater than . Notice that if is linear then the test always accepts and therefore it is onesided. This tests makes queries to .
The second test is testing if is in Linear assuming that it is in Linear. This is done by projecting the variables of into coordinates uniformly at random and learning (finding exactly) the projected function using the nonadaptive deterministic Hofmeister’s algorithm, [29], that makes queries. Since Linear, w.h.p., the relevant coordinates of the function are projected to different coordinates, and therefore, w.h.p., the learning gives a linear function that has exactly the same number of relevant coordinates as . The tester accepts if the number of relevant coordinates in the projected function is at most . If Linear, then the projected function is in Linear with probability 1 and therefore this test is onesided. This test makes queries.
We assumed that we can query . We now show how to query in strings so we can apply the above two tests. For this, the tester uses selfcorrector, [9]. To compute , the selfcorrector chooses a uniform random string and computes . Since is close to w.r.t. the uniform distribution, we have that for any string and an chosen uniformly at random, with probability at least , . Therefore, w.h.p., the selfcorrector computes correctly the values of in strings. If Linear then and , i.e., the selfcorrector gives the value of with probability . This shows that the above two tests are onesided.
Now, if is linear then . If is far from every function in Linear w.r.t. then it is far from w.r.t. .
In the final stage the tester tests whether is equal to or far from w.r.t. . Here again the tester uses selfcorrector. It asks for a sample according to the distribution of size and tests if for every , where are i.i.d. uniform random strings. If for all then it accepts, otherwise, it rejects. If is linear then for all and the tester accepts with probability . Now suppose is far from w.r.t. . Since is close to w.r.t. the uniform distribution and we have that, with probability at least , . Therefore, assuming the latter happens, then, with probability at least we have . Thus, w.h.p, there is such that and the tester rejects. This stage is onesided and makes queries.
2.2 Twosided Testers for Linear
As we mentioned in the introduction, the onesided query uniformdistribution tester for gives a twosided uniformdistribution query tester for . This is because, in the uniform distribution, the linear functions are far from each other and therefore, for any , if is close to a linear function then it is far from Linear. This is not true for any distribution , and therefore, cannot be applied here.
The algorithm in the previous subsection can be changed to a twosided tester for Linear as follows. The only part that should be changed is the test that is in Linear assuming that it is in Linear. We replace it with a test that is in Linear assuming that it is in Linear. The tester rejects if the number of relevant coordinates in the function that is learned is not equal to . This time the test is twosided. The reason is that the projection to variables does not guarantee (with probability ) that all the variables of are projected to different variables. Therefore, it may happen that is linear and the projection gives a linear function.
2.3 The Lower Bound for Onesided Testers
We first show the result for nonadaptive testers. Suppose there is a onesided nonadaptive uniform distribution tester for Linear that makes queries, where is the random seed of the tester and is the function that is tested. The algorithm has access to through a black box queries.
Consider the set of linear functions Linear where . Any linear function is far from every function in w.r.t. the uniform distribution. Therefore, using the tester , with probability at least , we can distinguish between any linear and any function in . By running the tester times, and accept if and only if all accept, we get a tester that asks queries and satisfies

If Linear then with probability , accepts.

If then, with probability at least , rejects.
By an averaging argument (i.e., fixing coins for ) and since , there exists a deterministic nonadaptive algorithm that makes queries such that

If Linear then accepts.

If then rejects.
Let , be the queries that makes. Let be a binary matrix where the th row of is and where if is a relevant coordinate in
. Then the vector of answers to the queries of
is . If for some , that is, the answers of the queries to are the same as the answer of the queries to , then rejects. Therefore, for every Linear and every we have . Now since is the set of all strings of weight , the sum (over the field ) of every columns of is not equal to and not equal to the sum of the last columns of , for all . In particular, if is the th column of , for every , and therefore . That is, the sum of every less or equal columns of the first columns of is not equal to zero. We then show that such matrix has at least rows. This implies that .For the lower bound for adaptive testers we take for some and get a matrix that the sum of every columns of is not zero. We then show that there exists where such a matrix must have at least rows.
3 The Testers for Linear and Linear
In this section we give the nonadaptive distributionfree onesided tester for Linear and the nonadaptive distributionfree twosided tester for Linear.
3.1 Notations
In this subsection, we give some notations that we use throughout the paper.
Denote . For and . For we denote by the set of all binary strings of length with coordinates indexed by . For and we write to denote the projection of over coordinates in . We denote by and the allone and allzero strings in , respectively. For a variable and a set , we denote by the string over coordinates in where for every , . For where and we write to denote their concatenation, i.e., the string in that agrees with over coordinates in and agrees with over coordinates in . For we denote .
For example, if , , , is a variable and then .
3.2 The Tester
Consider the tester TestLinear for Linear in Figure 2. The tester uses three procedures. The first is Selfcorrector that for an input chooses a uniform random and returns . The procedure BLR that is a nonadaptive uniformdistribution onesided tester for Linear. BLR makes queries for some constant , [9]. The third procedure is Hoffmeister’s Algorithm , a deterministic nonadaptive algorithm that exactly learns Linear over coordinates from black box queries. Hoffmeister’s Algorithm makes queries for some constant , [29].
To test Linear we use the same tester but change step 2 to:
(2) If the output is not in Linear then reject
We call this tester TestLinear.
3.3 Correctness of the Tester
In this section we prove
Theorem 5.
TestLinear is a nonadaptive distributionfree twosided tester for Linear that makes
queries.
Theorem 6.
TestLinear is a nonadaptive distributionfree onesided tester for Linear that makes
queries.
Proof.
Since there is no stage in the tester that uses the answers of the queries asked in previous ones, the tester is nonadaptive.
In Stage 1 the tester makes queries. In stage 2.1, queries. In stage 2.2, queries and in stage 3, queries. Therefore, the query complexity of the tester is .
We will assume that . For , (see the introduction and Table 1) the nonadaptive tester of Junta with the BLR tester and the selfcorrector gives a nonadaptive testers that makes queries.
Completeness: We first show the completeness for TestLinear that tests Linear. Suppose Linear. Then for every we have . Therefore, . In stage 1, BLR is onesided and therefore it does not reject. In stage 2.1, since are pairwise disjoint, the number of functions , , that are not identically zero is at most and therefore stage 2.1 does not reject. In stage 2.2, with probability at least , the relevant coordinates of fall into different and then is linear. Then, Hofmeister’s algorithm returns a linear function. Therefore, with probability at least the tester does not reject. Stage 3 does not reject since .
Now for the tester TestLinear, in stage 2.2, with probability the function is in . In fact, if relevant coordinates falls into the set then the coordinate (that correspond to the variable ) will be relevant in if and only if
is odd. Therefore, the tester does not reject.
Notice that TestLinear is onesided and TestLinear is twosided.
Soundness: We prove the soundness for TestLinear. The same proof also works for TestLinear. Suppose is far from Linear w.r.t. the distribution . We have four cases
 Case 1

: is far from Linear w.r.t. the uniform distribution.
 Case 2

: is close to Linear and is in .
 Case 3

: is close to Linear and is in .
 Case 4

: is close to Linear, is in and is far from w.r.t. .
For Case 1, if is far from Linear then, in stage 1, BLR rejects with probability .
For Cases 2 and 3, since is close to , for any fixed with probability at least (over a uniform random ), . Since stages 2.1 and 2.2 makes queries (to ), with probability at least , is computed correctly for all the queries in stages 2.1 and 2.2.
For Case 2, consider stage 2.1 of the tester. If is in then has more than relevant coordinates. The probability that less than or equal to of contains relevant coordinates of is at most
If contains the relevant coordinates then and therefore, for a uniform random , with probability at least , . Therefore, if at least of contains relevant coordinates then, by Chernoff bound, with probability at least , the counter “Count” is greater than . Therefore, for Case 2, if is in then, with probability at least , the tester rejects.
For Case 3, consider stage 2.2. If is in then has at most relevant coordinates. Then with probability at least , the relevant coordinates of fall into different and then Hofmeister’s algorithm returns a linear function with the same number of relevant coordinates as . Therefore stage 2.2 rejects with probability at least .
For Case 4, if is in Linear and is far from Linear w.r.t. , then is far from w.r.t. . Then for uniform random and ,
Therefore, with probability at most , stage 3 does not reject. ∎
4 Lower Bound
In this section we prove
Theorem 7.
Any nonadaptive uniformdistribution onesided tester for Linear must make at least queries.
Theorem 8.
Any adaptive uniformdistribution onesided tester for Linear must make at least queries.
4.1 Lower Bound for NonAdaptive Testers
We first show the result for nonadaptive testers.
Suppose there is a nonadaptive uniformdistribution onesided tester for Linear that makes queries, where is the random seed of the tester and is the function that is tested. The algorithm has access to through a black box queries.
Consider the set of linear functions Linear where . Any linear function is far from every function in w.r.t. the uniform distribution. Therefore, using the tester , with probability at least , can distinguish between any linear function and functions in . We boost the success probability to by running , times, and accept if and only if all accept. We get a tester that asks queries and satisfies

If Linear then with probability , accepts.

If then, with probability at least , rejects.
Therefore, the probability that for a uniform random , accepts for some is at most . Thus, there is a seed such that rejects for all (and accept for all Linear). This implies that there exists a deterministic nonadaptive algorithm that makes queries such that

If Linear then accepts.

If then rejects.
Let , be the queries that makes. Let be a binary matrix that it’s th row is . Let where iff is relevant coordinate in . Then the vector of answers to the queries of is . If for some , that is, the answers of the queries to are the same as the answers of the queries to , then rejects. Therefore, for every Linear and every we have . Now since is the set of all strings of weight , the sum (over the field ) of every columns of is not equal to (zero string) and not equal to the sum of the last columns of , for all . In particular, if is the th column of , for every , and therefore . That is, the sum of every less or equal columns of the first columns of is not equal to zero. We then show in Lemma 10 that such matrix has at least rows. This implies that .
Let be the minimum integer such that there exists a matrix over that the sum of any of its less than or equal columns is not . We have proved
Lemma 9.
Any nonadaptive uniformdistribution onesided tester for Linear must make at least queries.
Now to show that we prove the following result. This lemma follows from Hamming’s bound in coding theory. We give the proof for completeness
Lemma 10.
(Hamming’s Bound) We have
Proof.
Let be a matrix over that the sum of any of its less than or equal columns is not . Let and be a multiset. The strings in are distinct because, if for the contrary, we have two strings in that satisfies then (equal columns are cancelled) and , which is a contradiction. Therefore, and . ∎
4.2 Lower Bound for Adaptive Testers
For the lower bound for adaptive testers we take for some and get an adaptive algorithm that makes queries and satisfies

If Linear then with probability , accepts.

If then, with probability at least , rejects.
This implies that there exists a deterministic adaptive algorithm that makes queries such that

If Linear then accepts.

If then rejects.
Then, by the same argument as in the case of nonadaptive tester, we get a matrix that the sum of every columns of the first columns of is not zero. Let be the minimum integer such that there exists a matrix over that the sum of any of its columns is not . Then, we have proved that
Lemma 11.
Any adaptive uniformdistribution onesided tester for Linear must make at least queries.
In the next subsection, we show that there exists such that .
4.3 A Lower Bound for
In this section we prove
Lemma 12.
We have .
The idea of the proof is the following. For a set of integers an good matrix is a matrix that for every the sum of every columns of is not zero. A good matrix is a good matrix. We say that the matrix is almost good if there is a “small” number () of columns of that can be removed to get an good matrix. The concatenation (the matrix that contains the rows of both matrices) of almost good matrix with an almost good matrix is an almost good matrix.
Let and . The idea of the proof is to construct an almost good matrix by concatenating matrices where is good matrices for some . Then after removing small number () columns of we get a good matrix with rows and columns. By Hamming’s bound, Lemma 10, contains at least rows. Therefore, . So there is such that .
We now give more intuition to how to construct an almost good matrix from good matrices. Denote by . Let . We first show that if is good matrix then there exists a set of integers such that is almost good matrix and . The intuition is that if, for the contrary, there are many pairwise disjoint sets of columns that sum to that the great common divisor of their sizes divides , then the union of some of them gives
Comments
There are no comments yet.