The Correct Exponent for the Gotsman-Linial Conjecture

A (degree-d) polynomial threshold function is a function of the form f(x) = sgn(p(x)) for some (degree-d) polynomial d. The noise sensitivity of a boolean function is the probability that a small change in the input will lead to a change in the output. Gotsman and Linial proposed a conjecture for the correct bounds on the noise sensitivity of a polynomial threshold function in terms of its degree and number of variables. We will discuss recent work yielding bounds nearly as good as the conjectured correct ones.

See http://people.csail.mit.edu/madhu/reading-group/