Title: On the Sensitivity Conjecture
Speaker: Avishay Tal, IAS
Date: Monday, October 31, 2016 2:00 pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
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.