Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KUSHILEVITZ-MANSOUR:
Reports tagged with Kushilevitz-Mansour:
TR15-076 | 28th April 2015
Mahdi Cheraghchi, Piotr Indyk

#### Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

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

ISSN 1433-8092 | Imprint