The Fourier Transform of Boolean functions
Gil Kalai
Hebrew University, Jerusalem and I.A.S, Princeton
November 3,
4:15pm
refreshments at 3:45pm
2338
ABSTRACT

Boolean functions are of great interest in extremal combinatorics,
probability theory and complexity theory.
We will define and discuss the WelshFourier 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, edgeexpansion) of f.
3. If the support of f is small then the WF 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 WF coefficients are supported on "small" coefficients.
(OPEN PROBLEM: they are also supported on a few coefficients)
5. The connection of WF coefficients to stability of f under noise,
applications for questions in probability.
Among the question we ask: Better description of FW coefficients
of functions in AC0, "noise stability" for functions expressable
with threshold circuits, and more.
The lecture will be selfcontained and elementary.

Speaker's Contact Info: kalai(atsign)math.huji.ac.il
Return to seminar home page
Page loaded on October 26, 2000 at 01:52 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

