Speaker: Sun Xiaoming
Time: 2015-09-21 14:30-2015-09-21 15:30
Venue: FIT 1-222

Abstract:

The sensitivity conjecture of Nisan and Szegedy asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004.

In this talk I will survey some recently progress we made toward this conjecture. We prove tighter upper bounds for various complexity measures in terms of sensitivity. More precisely, we show that deg(f)^{1−o(1)} = O(2^s(f)) and C(f) ≤ 2^{s(f)−1} s(f); these in turn imply various corollaries regarding the relation between sensitivity and other complexity measures, such as block sensitivity, via known results. The gap between sensitivity and other complexity measures remains exponential but these results are the first improvement for this difficult problem that has been achieved in a decade. I will also discuss the sensitivity complexity of some special functions, for example graph properties.

Short Bio: