Boolean functions are of great interest in extremal combinatorics,
probability theory and complexity theory.
We will define and discuss the Walsh-Fourier coefficients f^(S)
of a Boolean function f and what can we learn from them. Some
results and applications will be presented but I will emphasize open
problems.
Among the fact we mention:
- (Parseval) The sum of squares of the Fourier coefficients is the
probability that f=1.
- The sum of f^(S) |S| is the sensitivity
(also known as the sum of influences, edge-expansion) of f.
- If the support of f is small then the Walsh-Fourier
coefficients are supported on "large" coefficients (coefficients where
|S| is large).
- If f can be described by a bounded depth circuit of small size
then the Walsh-Fourier coefficients are supported on "small" coefficients.
(Open problem: they are also supported on a few coefficients.)
- The connection of Walsh-Fourier coefficients to stability of
f under noise,
applications to questions in probability.
Among the question we ask: Better description of Fourier-Walsh
coefficients of functions in AC0, "noise stability" for functions
expressable with threshold circuits and more.
The lecture will be self-contained and elementary.
|