Recently, Viola (CCC'08) showed that the sum of d small-biased distributions fools degree-d polynomial tests; that is, every polynomial expression of degree at most d in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that ... more >>>
A small-biased distribution of bit sequences is defined as one withstanding GF(2)-linear tests for randomness, which are linear combinations of the bits themselves. We consider linear combinations over larger fields, specifically, GF(2^n) for n that divides the length of the bit sequence. Indeed, this means that we partition the bits ... more >>>