Seminar Room 1, Newton Institute
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.