0
$\begingroup$

As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$. Is it possible to improve this bound..?

Can somebody provide me an example of a Boolean function whose spectral norm is more than the degree of the Fourier expansion of $f$

$\endgroup$
3
  • 2
    $\begingroup$ In the comments to cstheory.stackexchange.com/questions/16730, you got an explicit example of a function whose spectral norm attains the bound $2^{n/2}$, and in particular is exponentially larger than the degree. Why do you not consider it to be an answer to your question, and why did you duplicate the question? $\endgroup$ Mar 6, 2013 at 17:29
  • $\begingroup$ I am looking for some simpler example $\endgroup$
    – Kumar
    Mar 6, 2013 at 18:39
  • $\begingroup$ I think as Emil said Emanuele's simple counterexample in his comment answers your question. Closing this one as a duplicate. $\endgroup$
    – Kaveh
    Mar 12, 2013 at 23:21

0