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.