| Linearity Testing in Characteristic Two (1997) | |||||||||||||||
Abstract | |||||||||||||||
| Let Dist(f; g) = Pr u [ f(u) 6=g(u) ] denote the relative distance between functions f; g mapping from a group G to a group H, and let Dist(f) denote the minimum, over all linear functions (homomorphisms) g, of Dist(f; g). Given a function f : G ! H we let Err(f) = Pr u;v [ f(u)+f(v) 6=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 particular the study of lower bounds on Err(f) in terms of Dist(f). The case 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 describe a Hadamard code of block length 2 n and for an arbitrary function f mapping GF(2) n to GF(2) the distance Dist(f) measures its distance to a Hadamard code (normalized so as to be a real number between 0 and 1). The quantity Err(f) is a parameter that is "easy to measure" and linearity testing studies the relations... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||