# influence of neighourhood points

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.

• 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?
– D.W.
Nov 17, 2022 at 0:28
• What's the motivation for the question, or the context in which you encountered it?
– D.W.
Nov 17, 2022 at 0:33

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$$.