Georgia Institute of Technology College of Sciences

Gil Kalai from the Hebrew University of Jerusalem will present the Algorithms, Combinatorics and Optimization (ACO) Distinguished Lecture on September 13, 2012 at 4:30 pm in Weber Space Science and Technology Building II (Weber SST II) Room 2.

There will be a reception in the lobby of Weber SST II at 4 p.m.

Gil Kalai, is the Henry and Manya Noskwith Professor of Mathematics at the Hebrew University of Jerusalem. He has a long term visiting position at Yale University and he is a frequent visitor to Microsoft Research.

Kalai's main research areas are combinatorics and convexity. He is interested in the combinatorial theory of convex polytopes, relations of combinatorics with topology and with Fourier analysis, Boolean functions, and threshold and isoperimetric phenomena. His interests also include applications to and connection with theoretical computer science, mathematical programming, probability theory, quantum computing, and game theory.

Kalai is the recipient of the 1992 Polya Prize, the 1993 Erdös Prize, the 1994 Fulkerson Prize and the 2012 Rothschild Prize. He is a member of the Center for the Study of Rationality as well as the Center for Quantum Information Science at the Hebrew University. He has served in several scientific committees at the university as well as at the national and international levels and he belongs to several editorial boards. In the last years he has been writing a scientific blog, Combinatorics and More, and has been active in various Internet mathematical activities.

Analysis of Boolean Functions, Influence and Noise

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. In a 1985 paper, Ben-Or and Linial, 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 Erdös and Rényi, 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.