Cheap and Secure Web Hosting Provider : See Now

# Sensitivity versus degree

, ,
Problem Detail:

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)$?

#### Answered By : Yuval Filmus

There is a function with degree $3^n$ and maximum sensitivity $6^n$, known as Kushilevitz's function. See page 14 of this survey.

We do know that average sensitivity is bounded by the degree. This is because average sensitivity is the same as total influence, and an easy computation shows that total influence is at most the degree.