Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and $\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x \oplus e_i)]$ be the total influence of a function under the standard definitions. Then does the following identity always hold?

$$ \langle f,Maj_n \rangle \leq c*\frac{\mathcal{I}(f)}{\mathcal{I}(Maj_n)} $$

where c is some universal constant. I believe it might be true but have not been able to prove it. I have tried some standard functions and they seem to work. I may be mistaken as I am very new to this area. Could you please suggest a way to prove it ? or some references regarding this

Thanks in advance

  • $\begingroup$ I think I can prove a weaker version fairly easily. The weaker version I think works for my application. However proofs of the statement are most welcome. $\endgroup$
    – NAg
    Jan 7, 2014 at 7:23
  • 1
    $\begingroup$ Can you prove it for a monotone function $f$? $\endgroup$ Jan 7, 2014 at 7:27
  • $\begingroup$ Would you have any example where c=1 is not enough? $\endgroup$ Jan 15, 2014 at 11:58
  • $\begingroup$ To both the above questions I dont think I can do either $\endgroup$
    – NAg
    Jan 26, 2014 at 15:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.