Gil Kalai

Abstract:   Boolean functions are functions f(x_1,...,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.

Here are some directions to Northeastern University. Lake Hall and Nightingale Hall can be best accessed from the entrance on the corner of Greenleaf Street and Leon Street. The two halls are connected, with no well-defined boundary in between. In particular, 509 Lake Hall is on the same corridor as 544 Nightingale Hall.

There is free parking available for people coming to the Colloquium at Northeastern's visitor parking (Rennaisance Garage). The entrance is from Columbus Avenue. If coming by car, you should park there and take the parking talon. After the lecture, you may pick up the payment coupon from Andrei Zelevinsky.