LINEARITY TESTING IN CHARACTERISTIC-2

Let Dist(f,g) = Pr-u[f(u) fg(u) not equal g(u)] denote the relative di stance between functions f, g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphi sms) g, of Dist(f,g). Given a function f: G --> H we let Err(f) = Pr-u ,Pr-v[f(u) + f(v) not equal f(u + v)] denote the rejection probability of the BLR (Blum-Luby-Rubinfeld) linearity test. Linearity testing is the study of the relationship between Err(f) and Dist(f), and in part icular the study of lower bounds on Err(f) in terms of Dist(f). The ca se we are interested in is when the underlying groups are G = GF(2)(n) and H = GF (2). In this case, the collection of linear functions desc ribe a Hadamard code of block length 2(n) and for an arbitrary functio n f mapping GF(2)(n) to GF(2) the distance Dist(f) measures its distan ce to a Hadamard code (normalized so as to be a real number between 0 and 1), The qnantity Err(f) is a parameter that is ''easy to measure'' and linearity testing studies the relationship of this parameter to t he distance of f. The code and corresponding test are used in the cons truction of efficient probabilistically checkable proofs and thence in the derivation of hardness of approximation results. In this context, improved analyses translate into better nonapproximability results. H owever, while several analyses of the relation of Err(f) to Dist(f) ar e known, none is tight. We present a description of the relationship b etween Err(f) and Dist(f) which is nearly complete in all its aspects, and entirely complete.(i.e., tight)in some. In particular we present functions L, U : [0, 1] --> [0, 1] such that for all x is an element o f [0, 1] we have L(x) less than or equal to Err(f) less than or equal to U(x) whenever Dist(f) = x, with the upper bound being tight on the whole range, and the lower bound tight on a large part of the range an d close on the rest. Part of our strengthening is obtained by showing a new connection between the linearity testing problem and Fourier ana lysis, a connection which may be of independent interest. Our results are used by Bellare, Goldreich, and Sudan to present the best known ha rdness results for Max-3SAT and other MaxSNP problems [7].