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

For any $00$, we give an efficient
deterministic construction of a linear subspace $V \subseteq
\R^n$, of dimension $(1-\epsilon)n$ in which the $\ell_p$ and
$\ell_r$ norms are the same up to a multiplicative factor of
$\poly(\epsilon^{-1})$ (after the correct normalization). As a
corollary we get a deterministic compressed sensing algorithm
more >>>

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>>