Harmonic Analysis

Harmonic or Fourier analysis is an indispensable tool in many branches of Electrical Engineering, Mathematics and Physics. By passing from a function defined on one space to its Fourier transform in another one gains valuable information. To take the most visible example, we are reminded of the spectrum of sound or light frequencies in an audio or video signal.

In recent years, these methods have made breakthrough contributions in Combinatorics and Computer Science. In a recent commemoratory volume is an essay by Jean Bourgain [2] on ``What can Combinatorics and Harmonic Analysis contribute to each other?''. Among other achievements, he mentions the brilliant work of Fields Medallist Timothy Gowers in obtaining a quantitative solution to the Erdös -Turan problem of arithmetic progressions (to which Endre Szemeredi had given a combinatorial solution before). Another area where these methods are playing an increasing role is in percolation theory (much to the annoyance of some people whom I heard complaining that they lose all the intuition when it goes over into another domain!). Finally mention must be made of the surprising role they have played in the theory of lower bounds in approximation algorithms in the work of near optimal inapproximability results of Johan Hastad. The reason for the ``unreasonable effectiveness'' of Fourier methods in combinatorics, is perhaps that in the words of Gowers, it does not matter that we perturb the coefficients of the characteristic function of a set and hence can concentrate on the higher coefficients, a remark whose mystery was partially dispelled in this series of lectures. A good reference for this series is the course notes developed independently by Babai and Umesh Vazirani (check their home pages/ ask them for a copy).

Jaikumar led us through a charming introduction to the world of Fourier transforms, onto some interesting applications. The first application was about resilience of Boolean functions: given a function $f$ from $n$ to $m$ bits with outputs uniformly distributed over the range, we say that $f$ is $t$-resilient if this uniform distribution is preserved even after fixing any $t \le n-m$ inputs. For instance, the XOR of $n$ bits is as resilient as they get, namely, $(n-1)$-resilient. How resilient can functions be at all? For functions from $3k$ to 2 bits, a simple construction using Fourier coefficients shows that one can have at most $2k-1$ resilience.

The second application was to do with influence of individual variables on the overall function, and sensitivity, another application mentioned by Bourgain's essay. It is easy to construct functions where the average influence of variables is low. With some more work, one can achieve low maximum influence. With clever use of the mysterious Bonami-Becker Inequality (however does one know when to pull out which such inequality? One was pulled out in the first talk while searching for balanced pairs, now another one here. We really need a nice oracle for this!), Kahn, Kim and Linial showed that if the Fourier transform of a balanced function is concentrated on large sets, then the average sensitivity of the function is high [15].

In a later talk, Meena described a proof due to Linial, Mansour and Nisan [13] that $AC^0$ functions have Fourier transforms concentrated on low sets, and thus have low average sensitivity, have good low-degree polynomial approximations over reals, are efficiently PAC-learnable, and are not good pseudo-random function generators.

Yet another very neat application Jaikumar described was using harmonic analysis to provide an upper bound on $N(H,\ell)$, the maximum number of copies of graph $H$ to be found in any graph with $\ell$ edges. Friedgut and Kahn have another proof using entropy. The harmonic analysis proof seemed much more simple and elegant to me, but it does not work for hypergraphs. Can't have it all ...

While on harmonic analysis, Pranab gave some explicit constructions for expanders. The constructions are very simple, but the proof of expansion properties needs bounds on graph eigenvalues, and the bounds are obtained by getting into matrix algebra and analyzing related Fourier transforms.

Pranab also talked about computing the quantum Fourier transform with polynomially many quantum gates. A crash intro to quantum computing, and a sketch of Shor's algorithm over cyclic groups, was followed by Kitaev's extension to Abelian groups.