Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

Mahdi Cheraghchi, Piotr Indyk

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+α} (\l…