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

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

We prove that a random linear code over \mathbb{F}_q, with probability arbitrarily close to 1, is list decodable at radius 1-1/q-\epsilon with list size L=O(1/\epsilon^2) and rate R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon))). Up to the polylogarithmic factor in 1/\epsilon and constant factors depending on q, this matches the lower bound L=\Omega_q(1/\epsilon^2) for the list ... more >>>

For every fixed constant \alpha > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform of an N-dimensional vector x \in \mathbb{R}^N in time k^{1+\alpha} (\log N)^{O(1)}. Specifically, the algorithm is given query access to x and computes a k-sparse \tilde{x} \in \mathbb{R}^N satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial (n^{\Omega(1)}) lower bound for an explicit range counting problem of n^3 convex polygons in \R^2 (each with n^{\tilde{O}(1)} facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

We establish strong inapproximability for finding the sparsest nonzero vector in a real subspace (where sparsity refers to the number of nonzero entries). Formally we show that it is NP-Hard (under randomized reductions) to approximate the sparsest vector in a subspace within any constant factor. By simple tensoring the inapproximability ... more >>>