The Fourier Transform of Boolean functions

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: 1. (Parseval) The sum of squares of the Fourier coefficients is the probability that f=1. 2. Sum \hat 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 W-F 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 W-F coefficients are supported on "small" coefficients. (OPEN PROBLEM: they are also supported on a few coefficients) 5. 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.

Speaker's Contact Info: kalai(at-sign)math.huji.ac.il