KTH/SU Mathematics Colloquium

2005-02-16

Gil Kalai (Hebrew University and Yale University)

Harmonic analysis of Boolean functions

Boolean functions are functions f(x_1,x_2,...x_n) where each variable as well as the value of the function itself attain the value 0 or 1. Boolean functions are fundamental objects in combinatorics, complexity theory, probability and other areas. Fourier analysis of Boolean functions plays important role in these areas since the mid eighties. Fourier analysis is related to discrete isoperimetric results, threshold phenomena for probabilistic models such as random graphs and percolations, low complexity classes, hardness of approximation and noise sensitivity. Hypercontractive estimates, namely results asserting that certain operators contract even when considered from 2-norm to p-norm for p>2 play (rather mysteriously) a crucial role. The talk, which will be self-contained, will discuss some of the developments in this area in a friendly way. Students are encouraged to attend.