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

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

Border complexity captures polynomials that can be approximated arbitrarily well by small algebraic circuits, and debordering asks how efficiently such an approximation can be converted into an exact computation. Debordering lies at the heart of the gap between Valiant's determinant versus permanent conjecture and its strengthening by Mulmuley and Sohoni ... more >>>