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)$?
Asked By : Turbo
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42120
0 comments:
Post a Comment
Let us know your responses and feedback