We show the following Reduction Lemma: any $\epsilon$-biased sample space with respect to (Boolean) linear tests is also $2\epsilon$-biased with respect to any system of independent linear tests. Combining this result with the previous constructions of $\epsilon$-biased sample space with respect to linear tests, we obtain the first efficient construction ... more >>>

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(N\log N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and {\em sub-linear} running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear time ... more >>>