The Fourier Transform of Boolean functions
Hebrew University, Jerusalem and I.A.S, Princeton
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)math.huji.ac.il
Return to seminar home page
Page loaded on October 26, 2000 at 01:52 PM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.