0
$\begingroup$

Im trying to understand the following question. Suppose $h,f:\{-1,1\}^n\rightarrow \{-1,1\}$ satisfy $\sum_x h(x)f(x)\leq 0.5$, then one can rewrite this as $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$. Can we use this statement to show: there exists $i\in [n]$ such that $\sum_i h(x)f(x)h(x^i)f(x^i)$ is small (where small here is unquantified, but im guessing it depends on $0.5$)? Also $x^i$ means the $i$th bit of $x$ is flipped.

In order to understand the above (either in proving its true or false), I started looking at $\sum_w h(w)f(w)\textbf{E}_i [h(w^i)f(w^i)]$ and seeing if it could be shown to be small as well. This requires one to understand the following: suppose $\textsf{Pr}_x [h(x)=f(x)]\leq 3/4$, then can we use that to say anything about the fraction of $w$s for which $h(w)=f(w)$ and $h(w^i)\neq f(w^i)$? Even this is unclear to me.

Any thoughts/counterexamples/references in this direction would be appreciated.

$\endgroup$
2
  • $\begingroup$ When you write $\sum_i$, do you mean $\sum_x \sum_i$? Do you mean there exists $x$ for which $\sum_i$ is small? Something else? $\endgroup$
    – D.W.
    Nov 17, 2022 at 0:28
  • $\begingroup$ What's the motivation for the question, or the context in which you encountered it? $\endgroup$
    – D.W.
    Nov 17, 2022 at 0:33

1 Answer 1

1
$\begingroup$

No. Suppose $h$ is the parity function and $f(x)=-h(x)$. Then $\sum_x h(x) f(x) = -2^n \le 0.5$, but $\sum_i h(x) f(x) h(x^i) f(x^i) = n$ (which is as large as it can get) for all $x$.

$\endgroup$

Your Answer

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

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