skip to content
 

Threshold behaviour

Presented by: 
G Kalai [HUJI & Yale]
Date: 
Monday 28th March 2011 - 10:00 to 11:00
Venue: 
INI Seminar Room 1
Abstract: 
In the lecture I will describe some results and problems regarding threshold behavior of Boolean and other functions.

1. Sharp threshold, the equal-slice measure and the Shapley value:

Result: Boolean functions with diminishing threshold window are precisely Boolean functions with diminishing maximum Shapley value.

Problem: Close the exponential gap in the quantitative version of this result,

2. Sharp threshold for larger alphabets (with Elchanan Mossel)

We show that sharp threshold behavior for monotone Boolean functions with symmetry extends to a larger alphabet. Large alphabets offer new challenges and new phenomena.

3. Problems about the relation between the expectation threshold and the threshold for graph properties and Boolean functions. (with Jeff Kahn). When probabilities get tiny matters are more difficult and more interesting.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons