Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

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

more >>>

Adi Akavia

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 ... more >>>