Analysis of Boolean Functions: advances and challenges

Date

November 25, 2013

Speaker

Gil Kalai

Affiliation

Hebrew University

Overview

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.

Speakers

Gil Kalai

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.