2
$\begingroup$

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

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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$? $\endgroup$ – Bread Winner May 4 '15 at 20:11
  • $\begingroup$ I never said that $\deg(f) \leq S(f)$. That isn't true. The maximum sensitivity can be much lower. $\endgroup$ – Yuval Filmus May 4 '15 at 21:03
  • $\begingroup$ 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)$? $\endgroup$ – Bread Winner May 4 '15 at 21:04
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Yuval Filmus May 4 '15 at 21:06
  • $\begingroup$ I believe this is also best gap known? $\endgroup$ – Bread Winner May 4 '15 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.