On the Sensitivity Conjecture
Location: Hill 705
Date & time: Monday, 31 October 2016 at 2:00PM - 2:11PM
Avishay Tal, IAS: In this talk, we plan to discuss several recent results regarding the sensitivity conjecture. The sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely, the number of Hamming neighbors of x with different f-value). The well-known sensitivity conjecture of Nisan-Szegedy states that every sensitivity s Boolean function can be computed by a polynomial over the reals of degree poly(s). The conjecture is still wide open, as the best known upper bounds on degree are exponential rather than polynomial in s.1. Based on joint work with Parikshit Gopalan, Rocco Servedio and Avi Wigderson, we prove an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L2) by a polynomial whose degree is O(s * log(1~epsilon)). This is the first improvement on the folklore bound of s~epsilon. Furthermore, we have examples demonstrating that our result is essentially tight.2. Based on joint work with Shalev Ben-David and Pooya Hatami, we present new super-quadratic separations between the sensitivity and various decision tree complexities.