Haifa University - Dept. of CS Theory Seminar

Speaker : Adi Akavia, IAS.

Title: "A combinatorial construction of almost-Ramanujan graphs using the zig-zag product ".

Date: Thursday, July 24.

Place: Haifa U. Education Building, room 570.

Time: 12:15 - 13:30

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 {\em 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 {\em significant Fourier coefficients}, that is, the Fourier coefficients whose magnitude is at least a $\tau$-fraction (say, 1\%) of the $\ell_2$-norm of the entire Fourier transform (\ie, the sum of squared Fourier coefficients).

In this paper we present an algorithm that finds the significant Fourier coefficients of functions $f$ over {\em any finite abelian group $G$}, which is:
   1. {\bf Local.} The running time and number of function entries read by the algorithm is polynomial in $\log N$, $1/\tau$ and $L_1(f)$ (for $N=\card G$ and $L_1(f)$ denoting the sum of absolute values of the Fourier coefficients of $f$).
   2. {\bf Input-oblivious.} The set of entries read by the algorithm depends only on the domain $G$ and on an upper bound on the sum of Fourier coefficients $L_1(f)$, and not on the input function $f$ itself. That is, the {\em same fixed} set of entries is read for {\em all} functions over the same domain and with the same upper bound on their sum of Fourier coefficients.
   3. {\bf Robust to noise.} The algorithm finds the significant Fourier coefficients of $f$, even if the function entries it receives are {\em corrupted by random noise}.
Furthermore, we present extensions of this algorithm to handle {\em adversarial noise} in running time {\em sub-linear} in the domain size.

Our algorithm improves on the prior input-oblivious algorithms in: (1) handling functions over {\em any finite abelian group}, (2) being {\em robust to noise}, and (3) achieving {\em better running time} in terms of $L_1(f)$.

We present applications of our algorithm to compressed sensing, to solving noisy variants of the Hidden Number Problem with advice, and to decoding polynomial rate Homomorphism codes and polynomial rate Multiplication codes.