Dept Banner
Dept Banner

Calendar

Download as iCal file

Discrete Math

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530