\begin{abstract}
The Fast Johnson-Lindenstrauss Transform was recently discovered by
Ailon and Chazelle as a technique for performing fast dimension
reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d,
k^3\})$, where $k$ is the target lower dimension. This beats the
naive $O(dk)$ achieved by multiplying by random dense matrices, as
noticed ... more >>>

Let $g(X)$ be a polynomial over a finite field ${\mathbb F}_q$ with degree $o(q^{1/2})$, and let $\chi$ be the quadratic residue character. We give a polynomial time algorithm to recover $g(X)$ (up to perfect square factors) given the values of $\chi \circ g$ on ${\mathbb F}_q$, with up to a ... more >>>