The University of Michigan Mathematics Colloquium
Fall 2000
December 5, 4:10-5:00, 1360 East Hall





The Fourier Transform of Boolean functions

Gil Kalai

Hebrew University and Institute for Advanced Study




Abstract

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:

  1. (Parseval) The sum of squares of the Fourier coefficients is the probability that f=1.
  2. The sum of f^(S) |S| is the sensitivity (also known as the sum of influences, edge-expansion) of f.
  3. If the support of f is small then the Walsh-Fourier coefficients are supported on "large" coefficients (coefficients where |S| is large).
  4. 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.)
  5. 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.