### DIMACS Theoretical Computer Science Seminar

Title: Locally & Universally Finding Significant Fourier Coefficients

Speaker: **Adi Akavia**, IAS

Date: Wednesday, October 29, 2008 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

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
sub-linear running time is necessary. Clearly, outputting the entire
Fourier transform in sub-linear time is infeasible. Nevertheless, in many
applications it suffices to find only the \tau-significant Fourier
coefficients, that is, the Fourier coefficients whose magnitude is at least a
\tau-fraction (say, 1%) of the total energy, i.e., the sum of squared Fourier
coefficients.

In this paper we present a deterministic algorithm that finds the
\tau-significant Fourier coefficients of functions f over any finite abelian
group G, which is:

- Local: The running time and number of function entries read by the
algorithm is polynomial in \log|G|, 1/\tau and L_1(f) (for L_1(f) denoting
the sum of absolute values of the Fourier coefficients of f).
- Universal: The algorithm reads the same set of function entries for all
functions f, as long as they are over the same domain and have a common upper
bound on L_1(f).
- Robust to noise: The algorithm finds the significant Fourier
coefficients of f, even if the function entries it receives are corrupted by
random noise.
Furthermore, we present extensions of this algorithm to handle adversarial
noise in running time sub-linear in the domain size.

Our result gives the first deterministic local algorithm for finding
significant Fourier coefficients that handle functions over Z_N, as well as
the first such algorithm that handles functions over arbitrary finite abelian
groups. Furthermore, our analysis is the first to show robustness to random
noise in the context of universal algorithms.

We present applications of our algorithm to compressed sensing; to proving
cryptographic bit security results; and to efficiently decoding polynomial
rate variants of Homomorphism codes and other concentrated and recoverable
codes. The universality of our algorithm is crucial to all the applications.