# Sensitivity versus degree

Given boolean function $f$, let $F$ denote the unique multiaffine real polynomial representing $f$.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$ where $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Is there an easy proof to show $S(f)\leq \mathsf{deg}(F)$?

There is a function with degree $3^n$ and maximum sensitivity $6^n$, known as Kushilevitz's function. See page 14 of this survey.
• I am a little confused. We know that $\mathsf{deg}(F)\leq BS(F)\leq \mathsf{deg}(F)^2$. From what you say, it seems, $\mathsf{deg}(F)\leq S(F)\leq BS(F)$. Wouldn't that mean, $\mathsf{deg}(F)\leq S(F)\leq BS(F)\leq \mathsf{deg}(F)^2\leq S(F)^2$? May 4, 2015 at 20:11
• I never said that $\deg(f) \leq S(f)$. That isn't true. The maximum sensitivity can be much lower. May 4, 2015 at 21:03
• oic you just gave a counter example. "The maximum sensitivity can be much lower" but not proven right? Is there an example of $S(f)<\mathsf{deg}(F)$? May 4, 2015 at 21:04
• It is conjectured that it can only be polynomially lower, but we don't know how to prove that. Here is a function of degree $n$ and maximum sensitivity $\sqrt{n}$: $\bigvee_{i=1}^{\sqrt{n}} \bigwedge_{j=1}^{\sqrt{n}} x_{ij}$. May 4, 2015 at 21:06