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.