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$

1 Answer 1

Reset to default
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$
    – Turbo
    May 4, 2015 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, 2015 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$
    – Turbo
    May 4, 2015 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, 2015 at 21:06
  • $\begingroup$ I believe this is also best gap known? $\endgroup$
    – Turbo
    May 4, 2015 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.