Abstract

For every fixed constant α > 0, we design a *deterministic* algorithm for computing the k-sparse Walsh-Hadamard
transform of an N-dimensional vector x  in time k^(1+α) polylog n. Specifically, the algorithm is given query access to x and computes an approximate  minimizer of the L1 approximation error ||y^ − x^||_1 over all k-sparse y^, where x^ denotes the spectrum of x. This is the first sub-linear time deterministic algorithm for this problem with sub-quadratic dependence on k.  
 
An important technical tool that we use is a construction of nearly optimal and linear lossless
condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan,
JACM 2009). 
 
Joint work with Mahdi Cheraghchi. Appeared in SODA'16.