摘要：We present a randomness efficient version of the linear noise operator T_Ï from boolean function analysis by constructing a sparse linear operator on the space of boolean functions {0,1}â¿ â' {0,1} with similar eigenvalue profile to T_Ï. The linear operator we construct is a direct consequence of a generalization of ε-biased sets to the product distribution ð'Y_p on {0,1}â¿ where the marginal of each coordinate is p = 1/2-1/2Ï. Such a generalization is a small support distribution that fools linear tests when the input of the test comes from ð'Y_p instead of the uniform distribution. We give an explicit construction of such a distribution that requires log n O_{p}(log log n log1/(ε)) bits of uniform randomness to sample from, where the p subscript hides O(log² 1/p) factors. When p and ε are constant, this yields a support size nearly linear in n, whereas previous best known constructions only guarantee a size of poly(n). Furthermore, our construction implies an explicitly constructible "sparse" noisy hypercube graph that is a small set expander.
