3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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$
    – Igor Shinkar
    Jan 7, 2014 at 7:27
  • $\begingroup$ Would you have any example where c=1 is not enough? $\endgroup$
    – Joseph Stack
    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

0

Reset to default

Your Answer

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