Degree and Sensitivity: tails of two distributions

Parikshit Gopalan, Rocco Servedio, Avishay Tal +1

The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisa…