The Fourier Transform of Boolean functions

Gil Kalai

Hebrew University, Jerusalem and I.A.S, Princeton

November 3,
refreshments at 3:45pm


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)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on October 26, 2000 at 01:52 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.