Analysis of Boolean Functions: advances and challenges

  • Gil Kalai | Hebrew University

Analysis of Boolean functions is a meeting point of combinatorics, probability theory, harmonic analysis, and the theory of computing. The lecture will describe some advances and challenges in this area. We will discuss discrete isoperimetric inequalities, influences, threshold phenomena for stochastic models, and noise-sensitivity as well as some connections with social choice theory.

Speaker Details

Gil Kalai is Professor of Mathematics at the Hebrew University of Jerusalem, He was the recipient of the Pólya Prize in 1992, the Erdos Prize of the Israel Mathematical Society in 1993, and the Fulkerson Prize in 1994. He is known for finding variants of the simplex algorithm that can be proven to run in subexponential time, for showing that every monotone property of graphs has a sharp phase transition and for solving Borsuk’s conjecture on the number of pieces needed to partition convex sets into subsets of smaller diameter and for other fundamental work in combinatorics and convexity.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks