Analysis of Boolean Functions, Influence and Noise

Thursday, September 13, 2012 - 4:30pm
Weber SST III Room 2
Speaker: 
Gil Kalai
Affiliation: 
Hebrew University of Jerusalem

A few results and two general conjectures regarding analysis of
Boolean functions, influence, and threshold phenomena will be presented.

  • Boolean functions are functions of n Boolean variables with values in
    {0,1}. They are important in combinatorics, theoretical computer science,
    probability theory, and game theory.
  • Influence: Causality is a topic of great interest everywhere, and if
    causality is not complicated enough, we can ask what is the influence one
    event has on another one. Ben-Or and Linial 1985 paper studied influence
    in the context of collective coin flipping -- a problem in theoretical
    computer science
    .
  • Fourier analysis: Over the last two decades, Fourier analysis of Boolean functions
    and related objects played a growing role in discrete mathematics, and
    theoretical computer science.
  • Threshold phenomena: Threshold phenomena refer to sharp transition in the
    probability of certain events depending on a parameter p near a critical
    value. A classic example that goes back to Erdos and Renyi, is the behavior
    of certain monotone properties of random graphs.

Influence of variables on Boolean functions is connected to their Fourier
analysis and threshold behavior, as well as to discrete isoperimetry
and noise sensitivity.

The first Conjecture to be described (with Friedgut) is called the
Entropy-Influence Conjecture. (It was featured on Tao's blog.) It gives a
far reaching extension to the KKL theorem, and theorems by Friedgut,
Bourgain, and me.

The second Conjecture (with Kahn) proposes a far-reaching generalization to
results by Friedgut, Bourgain and Hatami.

References

  1. J. Bourgain and G. Kalai, Influences of variables and threshold
    intervals under group symmetries
    GAFA 7 (1997), 438-461.
  2. H. Hatami, A structure theorem for Boolean functions with small total
    influences
    , Ann. of Math., to appear.
  3. J. Kahn and G. Kalai, Thresholds and expectation thresholds, Comb.,
    Prob. and Comp., 16 (2007), 495-502.

There will be a reception in the lobby of the SST III at 4PM