The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

DAN

Seminar

Threshold behaviour

Kalai, G (HUJI & Yale)
Monday 28 March 2011, 10:00-11:00

Seminar Room 1, Newton Institute

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.

Video

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.

Back to top ∧