0
$\begingroup$

Given a function $f:\{0,1\}^n\rightarrow \{0,1\}$, is it true that for any $S,T\subseteq[n]$, such that $S\cap T =\phi$, then $\hat{f}(S\cup T)\leq \hat{f}(S)$? It seems so to me cause, if if you just write out the fourier expansion of the former and just upper bound the negative terms corresponding to the T, by replacing them with 1, you get the RHS. But the statement overallseems counterintuitive to me, cause it seems like $\hat{f}(\phi)$ is the largest then for $any$ boolean function.

$\endgroup$
0
$\begingroup$

Take the Majority function on 3-bits as an example it is not true. $\widehat{Maj}({1})\leq \widehat{Maj}({1,2,3})$.

$\endgroup$

Your Answer

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