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

Reset to default
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$.

Improve this answer
$\endgroup$

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.

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