The Fourier Transform of Boolean Functions

Gil Kalai, Hebrew University, Jerusalem, and IAS, Princeton
November 28, 4:30 PM, Rutgers Univ. Hill CORE building, Room 431


Abstract.

Boolean functions are of great interest in extremal combinatorics, probability theory and complexity theory.

We will define and discuss the Welsh-Fourier coefficients \hat 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.
  • Sum \hat 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 W-F 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 W-F coefficients are supported on "small" coefficients. (OPEN PROBLEM: they are also supported on a few coefficients)
  • The connection of W-F coefficients to stability of f under noise, applications for questions in probability.

    Among the question we ask: Better description of F-W coefficients of functions in AC0, "noise stability" for functions expressable with threshold circuits and more.

    The lecture will be self contained and elementary.



    Back to Discrete Math/Theory of Computing seminar