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 '14 at 7:23
  • 1
    $\begingroup$ Can you prove it for a monotone function $f$? $\endgroup$ – Igor Shinkar Jan 7 '14 at 7:27
  • $\begingroup$ Would you have any example where c=1 is not enough? $\endgroup$ – Joseph Stack Jan 15 '14 at 11:58
  • $\begingroup$ To both the above questions I dont think I can do either $\endgroup$ – NAg Jan 26 '14 at 15:41

Your Answer

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

Browse other questions tagged or ask your own question.